{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Accounts Merge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #hash-table #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #哈希表 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: accountsMerge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #账户合并"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个列表 <code>accounts</code>，每个元素 <code>accounts[i]</code>&nbsp;是一个字符串列表，其中第一个元素 <code>accounts[i][0]</code>&nbsp;是&nbsp;<em>名称 (name)</em>，其余元素是 <em><strong>emails</strong> </em>表示该账户的邮箱地址。</p>\n",
    "\n",
    "<p>现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。</p>\n",
    "\n",
    "<p>合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 <strong>按字符 ASCII 顺序排列</strong> 的邮箱地址。账户本身可以以 <strong>任意顺序</strong> 返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>accounts = [[\"John\", \"johnsmith@mail.com\", \"john00@mail.com\"], [\"John\", \"johnnybravo@mail.com\"], [\"John\", \"johnsmith@mail.com\", \"john_newyork@mail.com\"], [\"Mary\", \"mary@mail.com\"]]\n",
    "<b>输出：</b>[[\"John\", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  [\"John\", \"johnnybravo@mail.com\"], [\"Mary\", \"mary@mail.com\"]]\n",
    "<b>解释：</b>\n",
    "第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 \"johnsmith@mail.com\"。 \n",
    "第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。\n",
    "可以以任何顺序返回这些列表，例如答案 [['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，\n",
    "['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']] 也是正确的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>accounts = [[\"Gabe\",\"Gabe0@m.co\",\"Gabe3@m.co\",\"Gabe1@m.co\"],[\"Kevin\",\"Kevin3@m.co\",\"Kevin5@m.co\",\"Kevin0@m.co\"],[\"Ethan\",\"Ethan5@m.co\",\"Ethan4@m.co\",\"Ethan0@m.co\"],[\"Hanzo\",\"Hanzo3@m.co\",\"Hanzo1@m.co\",\"Hanzo0@m.co\"],[\"Fern\",\"Fern5@m.co\",\"Fern1@m.co\",\"Fern0@m.co\"]]\n",
    "<strong>输出：</strong>[[\"Ethan\",\"Ethan0@m.co\",\"Ethan4@m.co\",\"Ethan5@m.co\"],[\"Gabe\",\"Gabe0@m.co\",\"Gabe1@m.co\",\"Gabe3@m.co\"],[\"Hanzo\",\"Hanzo0@m.co\",\"Hanzo1@m.co\",\"Hanzo3@m.co\"],[\"Kevin\",\"Kevin0@m.co\",\"Kevin3@m.co\",\"Kevin5@m.co\"],[\"Fern\",\"Fern0@m.co\",\"Fern1@m.co\",\"Fern5@m.co\"]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= accounts.length &lt;= 1000</code></li>\n",
    "\t<li><code>2 &lt;= accounts[i].length &lt;= 10</code></li>\n",
    "\t<li><code>1 &lt;= accounts[i][j].length &lt;= 30</code></li>\n",
    "\t<li><code>accounts[i][0]</code> 由英文字母组成</li>\n",
    "\t<li><code>accounts[i][j] (for j &gt; 0)</code> 是有效的邮箱地址</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [accounts-merge](https://leetcode.cn/problems/accounts-merge/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [accounts-merge](https://leetcode.cn/problems/accounts-merge/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"John\",\"johnsmith@mail.com\",\"john_newyork@mail.com\"],[\"John\",\"johnsmith@mail.com\",\"john00@mail.com\"],[\"Mary\",\"mary@mail.com\"],[\"John\",\"johnnybravo@mail.com\"]]', '[[\"Gabe\",\"Gabe0@m.co\",\"Gabe3@m.co\",\"Gabe1@m.co\"],[\"Kevin\",\"Kevin3@m.co\",\"Kevin5@m.co\",\"Kevin0@m.co\"],[\"Ethan\",\"Ethan5@m.co\",\"Ethan4@m.co\",\"Ethan0@m.co\"],[\"Hanzo\",\"Hanzo3@m.co\",\"Hanzo1@m.co\",\"Hanzo0@m.co\"],[\"Fern\",\"Fern5@m.co\",\"Fern1@m.co\",\"Fern0@m.co\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "        # 根节点所在集合的所有账户\n",
    "        self.accounts = {}\n",
    "        \n",
    "    def find(self,x):\n",
    "        if not self.father[x]: return x\n",
    "        \n",
    "        # 递归的路径压缩处理\n",
    "        self.father[x] = self.find(self.father[x])\n",
    "        \n",
    "        return self.father[x]\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        root_x,root_y = self.find(x),self.find(y)\n",
    "        \n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        \n",
    "        # 按秩合并，更新根节点和所属的账户\n",
    "        if len(self.accounts[root_x]) > len(self.accounts[root_y]):\n",
    "            self.father[root_y] = root_x\n",
    "            self.accounts[root_x] += self.accounts[root_y]\n",
    "            del self.accounts[root_y]\n",
    "        else:\n",
    "            self.father[root_x] = root_y\n",
    "            self.accounts[root_y] += self.accounts[root_x]\n",
    "            del self.accounts[root_x]\n",
    "    \n",
    "    def add(self,x):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "            self.accounts[x] = [x]\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        uf = UnionFind()\n",
    "        for account in accounts:\n",
    "            # 找到姓名和主账户\n",
    "            name,master = account[0],account[1]\n",
    "            uf.add((name,master))\n",
    "            \n",
    "            # 和其余的账户一一合并\n",
    "            account = list(set(account[2:]))\n",
    "            for i in range(len(account)):\n",
    "                uf.add((name,account[i]))\n",
    "                uf.merge((name,master),(name,account[i]))\n",
    "        \n",
    "        res = []\n",
    "        for key,value in uf.father.items():\n",
    "            # 是根节点\n",
    "            if not value:\n",
    "                # 添加user\n",
    "                usr = [uf.accounts[key][0][0]]\n",
    "                acc = []\n",
    "                # 添加账户\n",
    "                for account in uf.accounts[key]:\n",
    "                    acc.append(account[1])\n",
    "                    \n",
    "                res.append(usr + sorted(acc))\n",
    "                \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "        # 根节点所在集合的所有账户\n",
    "        self.accounts = {}\n",
    "        \n",
    "    def find(self,x):\n",
    "        if not self.father[x]: return x\n",
    "        \n",
    "        # 递归的路径压缩处理\n",
    "        self.father[x] = self.find(self.father[x])\n",
    "        \n",
    "        return self.father[x]\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        root_x,root_y = self.find(x),self.find(y)\n",
    "        \n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        \n",
    "        # 按秩合并，更新根节点和所属的账户\n",
    "        if len(self.accounts[root_x]) > len(self.accounts[root_y]):\n",
    "            self.father[root_y] = root_x\n",
    "            self.accounts[root_x] += self.accounts[root_y]\n",
    "            del self.accounts[root_y]\n",
    "        else:\n",
    "            self.father[root_x] = root_y\n",
    "            self.accounts[root_y] += self.accounts[root_x]\n",
    "            del self.accounts[root_x]\n",
    "    \n",
    "    def add(self,x):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "            self.accounts[x] = [x]\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        uf = UnionFind()\n",
    "        for account in accounts:\n",
    "            # 找到姓名和主账户\n",
    "            name,master = account[0],account[1]\n",
    "            uf.add((name,master))\n",
    "            \n",
    "            # 和其余的账户一一合并\n",
    "            account = list(set(account[2:]))\n",
    "            for i in range(len(account)):\n",
    "                uf.add((name,account[i]))\n",
    "                uf.merge((name,master),(name,account[i]))\n",
    "        \n",
    "        res = []\n",
    "        for key,value in uf.father.items():\n",
    "            # 是根节点\n",
    "            if not value:\n",
    "                # 添加user\n",
    "                usr = [uf.accounts[key][0][0]]\n",
    "                acc = []\n",
    "                # 添加账户\n",
    "                for account in uf.accounts[key]:\n",
    "                    acc.append(account[1])\n",
    "                    \n",
    "                res.append(usr + sorted(acc))\n",
    "                \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def build_graph(self,accounts):\n",
    "        # 构建无向图，每个邮箱为一个节点，同一个账户的邮箱全部相连\n",
    "        # 有多少连通分量，就有多少独立的账户\n",
    "        # 该字典，键为一个邮箱，值为与其相连的所有邮箱\n",
    "        graph = collections.defaultdict(list)\n",
    "        for account in accounts:\n",
    "            master = account[1]\n",
    "            # 对剩余账户做一个去重\n",
    "            for email in list(set(account[2:])):\n",
    "                graph[master].append(email)\n",
    "                graph[email].append(master)\n",
    "        \n",
    "        return graph\n",
    "    \n",
    "    def dfs(self,email,graph,visited,emails):\n",
    "        \"\"\"\n",
    "        深搜遍历\n",
    "        \"\"\"\n",
    "        # 已经访问过的就剪枝\n",
    "        if email in visited:\n",
    "            return \n",
    "        \n",
    "        visited.add(email)\n",
    "        emails.append(email)\n",
    "        \n",
    "        # 对邻居节点继续深搜\n",
    "        for neighbor in graph[email]:\n",
    "            self.dfs(neighbor,graph,visited,emails)\n",
    "    \n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        graph = self.build_graph(accounts)\n",
    "\n",
    "        res = []\n",
    "        visited = set()\n",
    "        for account in accounts:\n",
    "            emails = []# 存储该账户的所有邮箱\n",
    "            # 深度优先遍历，作为键的第一个邮箱如果已经被前者关联，则直接剪枝\n",
    "            self.dfs(account[1],graph,visited,emails)\n",
    "            #如果是相同用户出现过了，则全会被剪枝，res不会添加\n",
    "            if emails:\n",
    "                res.append([account[0]] + sorted(emails))\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "\n",
    "    def __init__(self):\n",
    "\n",
    "        self.father = {}\n",
    "\n",
    "        # 根节点所在集合的所有账户\n",
    "\n",
    "        self.accounts = {}\n",
    "\n",
    "        \n",
    "\n",
    "    def find(self,x):\n",
    "\n",
    "        if not self.father[x]: return x\n",
    "\n",
    "        \n",
    "\n",
    "        # 递归的路径压缩处理\n",
    "\n",
    "        self.father[x] = self.find(self.father[x])\n",
    "\n",
    "        \n",
    "\n",
    "        return self.father[x]\n",
    "\n",
    "    \n",
    "\n",
    "    def merge(self,x,y):\n",
    "\n",
    "        root_x,root_y = self.find(x),self.find(y)\n",
    "\n",
    "        \n",
    "\n",
    "        if root_x == root_y:\n",
    "\n",
    "            return\n",
    "\n",
    "        \n",
    "\n",
    "        # 按秩合并，更新根节点和所属的账户\n",
    "\n",
    "        if len(self.accounts[root_x]) > len(self.accounts[root_y]):\n",
    "\n",
    "            self.father[root_y] = root_x\n",
    "\n",
    "            self.accounts[root_x] += self.accounts[root_y]\n",
    "\n",
    "            del self.accounts[root_y]\n",
    "\n",
    "        else:\n",
    "\n",
    "            self.father[root_x] = root_y\n",
    "\n",
    "            self.accounts[root_y] += self.accounts[root_x]\n",
    "\n",
    "            del self.accounts[root_x]\n",
    "\n",
    "    \n",
    "\n",
    "    def add(self,x):\n",
    "\n",
    "        if x not in self.father:\n",
    "\n",
    "            self.father[x] = None\n",
    "\n",
    "            self.accounts[x] = [x]\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "\n",
    "        uf = UnionFind()\n",
    "\n",
    "        for account in accounts:\n",
    "\n",
    "            # 找到姓名和主账户\n",
    "\n",
    "            name,master = account[0],account[1]\n",
    "\n",
    "            uf.add((name,master))\n",
    "\n",
    "            \n",
    "\n",
    "            # 和其余的账户一一合并\n",
    "\n",
    "            account = list(account[2:])\n",
    "\n",
    "            for i in range(len(account)):\n",
    "\n",
    "                uf.add((name,account[i]))\n",
    "\n",
    "                uf.merge((name,master),(name,account[i]))\n",
    "\n",
    "        \n",
    "\n",
    "        res = []\n",
    "\n",
    "        for key,value in uf.father.items():\n",
    "\n",
    "            # 是根节点\n",
    "\n",
    "            if not value:\n",
    "\n",
    "                # 添加user\n",
    "\n",
    "                usr = [uf.accounts[key][0][0]]\n",
    "\n",
    "                acc = []\n",
    "\n",
    "                # 添加账户\n",
    "\n",
    "                for account in uf.accounts[key]:\n",
    "\n",
    "                    acc.append(account[1])\n",
    "\n",
    "                    \n",
    "\n",
    "                res.append(usr + sorted(acc))\n",
    "\n",
    "                \n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#copy\n",
    "class unionfind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "        self.accounts = {}\n",
    "    def find(self,x):\n",
    "        if not self.father[x]:\n",
    "            return x\n",
    "        self.father[x]=  self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "    def merge(self,x,y):\n",
    "        rootx,rooty = self.find(x),self.find(y)\n",
    "        if rootx == rooty:\n",
    "            return \n",
    "        if len(self.accounts[rootx]) > len(self.accounts[rooty]):\n",
    "            self.father[rooty] = rootx\n",
    "            self.accounts[rootx] += self.accounts[rooty]\n",
    "            del self.accounts[rooty]\n",
    "        else:\n",
    "            self.father[rootx] = rooty\n",
    "            self.accounts[rooty] += self.accounts[rootx]\n",
    "            del self.accounts[rootx]\n",
    "    def add(self,x):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "            self.accounts[x] =[x]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        uf = unionfind()\n",
    "        for account in accounts:\n",
    "            name,master = account[0],account[1]\n",
    "            uf.add((name,master))\n",
    "\n",
    "            account = list(set(account[2:]))\n",
    "            for i in range(len(account)):\n",
    "                uf.add((name,account[i]))\n",
    "                uf.merge((name,master),(name,account[i]))\n",
    "        res = []\n",
    "        for k,v in uf.father.items():\n",
    "            if not v:\n",
    "                usr = [uf.accounts[k][0][0]]\n",
    "                acc = []\n",
    "                for account in uf.accounts[k]:\n",
    "                    acc.append(account[1])\n",
    "                \n",
    "                res.append(usr+ sorted(acc))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "        # 根节点所在集合的所有账户\n",
    "        self.accounts = {}\n",
    "        \n",
    "    def find(self,x):\n",
    "        if not self.father[x]: return x\n",
    "        \n",
    "        # 递归的路径压缩处理\n",
    "        self.father[x] = self.find(self.father[x])\n",
    "        \n",
    "        return self.father[x]\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        root_x,root_y = self.find(x),self.find(y)\n",
    "        \n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        \n",
    "        # 按秩合并，更新根节点和所属的账户\n",
    "        if len(self.accounts[root_x]) > len(self.accounts[root_y]):\n",
    "            self.father[root_y] = root_x\n",
    "            self.accounts[root_x] += self.accounts[root_y]\n",
    "            del self.accounts[root_y]\n",
    "        else:\n",
    "            self.father[root_x] = root_y\n",
    "            self.accounts[root_y] += self.accounts[root_x]\n",
    "            del self.accounts[root_x]\n",
    "    \n",
    "    def add(self,x):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "            self.accounts[x] = [x]\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        uf = UnionFind()\n",
    "        for account in accounts:\n",
    "            # 找到姓名和主账户\n",
    "            name,master = account[0],account[1]\n",
    "            uf.add((name,master))\n",
    "            \n",
    "            # 和其余的账户一一合并\n",
    "            account = list(set(account[2:]))\n",
    "            for i in range(len(account)):\n",
    "                uf.add((name,account[i]))\n",
    "                uf.merge((name,master),(name,account[i]))\n",
    "        \n",
    "        res = []\n",
    "        for key,value in uf.father.items():\n",
    "            # 是根节点\n",
    "            if not value:\n",
    "                # 添加user\n",
    "                usr = [uf.accounts[key][0][0]]\n",
    "                acc = []\n",
    "                # 添加账户\n",
    "                for account in uf.accounts[key]:\n",
    "                    acc.append(account[1])\n",
    "                    \n",
    "                res.append(usr + sorted(acc))\n",
    "                \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father={}\n",
    "        self.account={}\n",
    "        \n",
    "    def find(self, x):\n",
    "        if not self.father[x]:\n",
    "            return x\n",
    "        self.father[x]=self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        px, py=self.find(x), self.find(y)\n",
    "        if px == py:\n",
    "            return\n",
    "        \n",
    "        if len(self.account[px])>len(self.account[py]):\n",
    "            self.father[py]=px\n",
    "            self.account[px] += self.account[py]\n",
    "            del self.account[py]\n",
    "        else:\n",
    "            self.father[px]=py\n",
    "            self.account[py] += self.account[px]\n",
    "            del self.account[px]\n",
    "    \n",
    "    def add(self, x):\n",
    "        if x not in self.father:\n",
    "            self.father[x]=None\n",
    "            self.account[x]=[x]\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        uf=UnionFind()\n",
    "        for account in accounts:\n",
    "            name, master=account[0],account[1]\n",
    "            uf.add((name, master))\n",
    "            account=list(set(account[2:]))\n",
    "            for i in range(len(account)):\n",
    "                uf.add((name, account[i]))\n",
    "                uf.merge((name, master), (name, account[i]))\n",
    "        res=[]\n",
    "        for key, val in uf.father.items():\n",
    "            if not val:\n",
    "                usr=[uf.account[key][0][0]]\n",
    "                acc=[]\n",
    "                for a in uf.account[key]:\n",
    "                    acc.append(a[1])\n",
    "                res.append(usr+sorted(acc))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        p = defaultdict(str) \n",
    "        def find(x):\n",
    "            if x not in p:\n",
    "                p[x] = x \n",
    "                return p[x] \n",
    "            if x == p[x]:\n",
    "                return x \n",
    "            p[x] = find(p[x]) \n",
    "            return p[x] \n",
    "        def un(x, y):\n",
    "            fx, fy =find(x), find(y) \n",
    "            if fx == fy:\n",
    "                return False \n",
    "            else:\n",
    "                p[fy] = fx \n",
    "                return True \n",
    "        name = defaultdict(str) \n",
    "        for vec in accounts:\n",
    "            m = len(vec)\n",
    "            fx = find(vec[1]) \n",
    "            for i in range(2,m):\n",
    "                un(fx,vec[i]) \n",
    "            fx = find(vec[1]) \n",
    "            name[fx] = vec[0] \n",
    "        ans = defaultdict(list) \n",
    "        for ac in p:\n",
    "            fx = find(ac) \n",
    "            ans[fx].append(ac) \n",
    "        return [[name[fx]] + sorted(vec) for fx, vec in ans.items()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "        # 根节点所在集合的所有账户\n",
    "        self.accounts = {}\n",
    "        \n",
    "    def find(self,x):\n",
    "        if not self.father[x]: return x\n",
    "        \n",
    "        # 递归的路径压缩处理\n",
    "        self.father[x] = self.find(self.father[x])\n",
    "        \n",
    "        return self.father[x]\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        root_x,root_y = self.find(x),self.find(y)\n",
    "        \n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        \n",
    "        # 按秩合并，更新根节点和所属的账户\n",
    "        if len(self.accounts[root_x]) > len(self.accounts[root_y]):\n",
    "            self.father[root_y] = root_x\n",
    "            self.accounts[root_x] += self.accounts[root_y]\n",
    "            del self.accounts[root_y]\n",
    "        else:\n",
    "            self.father[root_x] = root_y\n",
    "            self.accounts[root_y] += self.accounts[root_x]\n",
    "            del self.accounts[root_x]\n",
    "    \n",
    "    def add(self,x):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "            self.accounts[x] = [x]\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        uf = UnionFind()\n",
    "        for account in accounts:\n",
    "            # 找到姓名和主账户\n",
    "            name,master = account[0],account[1]\n",
    "            uf.add((name,master))\n",
    "            \n",
    "            # 和其余的账户一一合并\n",
    "            account = list(set(account[2:]))\n",
    "            for i in range(len(account)):\n",
    "                uf.add((name,account[i]))\n",
    "                uf.merge((name,master),(name,account[i]))\n",
    "        \n",
    "        res = []\n",
    "        for key,value in uf.father.items():\n",
    "            # 是根节点\n",
    "            if not value:\n",
    "                # 添加user\n",
    "                usr = [uf.accounts[key][0][0]]\n",
    "                acc = []\n",
    "                # 添加账户\n",
    "                for account in uf.accounts[key]:\n",
    "                    acc.append(account[1])\n",
    "                    \n",
    "                res.append(usr + sorted(acc))\n",
    "                \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "        # 根节点所在集合的所有账户\n",
    "        self.accounts = {}\n",
    "        \n",
    "    def find(self,x):\n",
    "        if not self.father[x]: return x\n",
    "        \n",
    "        # 递归的路径压缩处理\n",
    "        self.father[x] = self.find(self.father[x])\n",
    "        \n",
    "        return self.father[x]\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        root_x,root_y = self.find(x),self.find(y)\n",
    "        \n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        \n",
    "        # 按秩合并，更新根节点和所属的账户\n",
    "        if len(self.accounts[root_x]) > len(self.accounts[root_y]):\n",
    "            self.father[root_y] = root_x\n",
    "            self.accounts[root_x] += self.accounts[root_y]\n",
    "            del self.accounts[root_y]\n",
    "        else:\n",
    "            self.father[root_x] = root_y\n",
    "            self.accounts[root_y] += self.accounts[root_x]\n",
    "            del self.accounts[root_x]\n",
    "    \n",
    "    def add(self,x):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "            self.accounts[x] = [x]\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        uf = UnionFind()\n",
    "        for account in accounts:\n",
    "            # 找到姓名和主账户\n",
    "            name,master = account[0],account[1]\n",
    "            uf.add((name,master))\n",
    "            \n",
    "            # 和其余的账户一一合并\n",
    "            account = list(set(account[2:]))\n",
    "            for i in range(len(account)):\n",
    "                uf.add((name,account[i]))\n",
    "                uf.merge((name,master),(name,account[i]))\n",
    "        res = []\n",
    "        for key,value in uf.father.items():\n",
    "            # 是根节点\n",
    "            if not value:\n",
    "                # 添加user\n",
    "                usr = [uf.accounts[key][0][0]]\n",
    "                acc = []\n",
    "                # 添加账户\n",
    "                for account in uf.accounts[key]:\n",
    "                    acc.append(account[1])\n",
    "                    \n",
    "                res.append(usr + sorted(acc))\n",
    "                \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        # assign each unique email a vertex index\n",
    "        hashmap = {}\n",
    "        i = 0\n",
    "        for account in accounts:\n",
    "            name, emails = account[0], account[1:]\n",
    "            for email in emails:\n",
    "                if email not in hashmap:\n",
    "                    hashmap[email] = (i, name)\n",
    "                    i += 1\n",
    "        \n",
    "        UF = UnionFind(i)\n",
    "        for account in accounts:\n",
    "            emails = account[1:]\n",
    "            for i in range(len(emails)-1):\n",
    "                u, v = hashmap[emails[i]][0], hashmap[emails[i+1]][0]\n",
    "                UF.unionSet(u, v)  \n",
    "        \n",
    "        ans = defaultdict(list)\n",
    "        for email in hashmap:\n",
    "            root = UF.findSet(hashmap[email][0])\n",
    "            ans[root].append(email)\n",
    "        \n",
    "        ans = [[hashmap[emails[0]][1]] + sorted(emails) for emails in ans.values()]\n",
    "\n",
    "        return ans \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        \"\"\"\n",
    "        build m disjoint sets from n nodes\n",
    "        T: O(N)\n",
    "        \"\"\"\n",
    "        self.parents = list(range(n))    \n",
    "        self.ranks = [0] * n            \n",
    "    \n",
    "    def findSet(self, i: int) -> int:\n",
    "        \"\"\"return root of node i's set\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "           path-compression  \n",
    "           Recursion\n",
    "        \"\"\"\n",
    "        if self.parents[i] == i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parents[i] = self.findSet(self.parents[i])\n",
    "            return self.parents[i]\n",
    "        \n",
    "    \n",
    "    def unionSet(self, i: int, j: int) -> None:\n",
    "        \"\"\"若节点i和节点j来自2个不同的互斥集合，将两个集合合并 \n",
    "           union by rank   矮树作为高树的子树\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        ip, jp = self.findSet(i), self.findSet(j)\n",
    "\n",
    "        # 若两个节点来自同一互斥集合，返回\n",
    "        if ip == jp:\n",
    "            return \n",
    "\n",
    "        # 若A树矮，B树高，A树连到B树的根节点上，新树rank不变\n",
    "        if self.ranks[ip] < self.ranks[jp]:\n",
    "            self.parents[ip] = jp\n",
    "\n",
    "        # 若B树矮，A树高，B树连到A树的根节点上，新树rank不变\n",
    "        elif self.ranks[jp] < self.ranks[ip]:\n",
    "            self.parents[jp] = ip\n",
    "\n",
    "        # 若两树等高，任选一种方案，新树 rank +1\n",
    "        else:\n",
    "            self.parents[jp] = ip\n",
    "            self.ranks[ip] += 1\n",
    "\n",
    "    \n",
    "    def isSameSet(self, i: int, j: int) -> bool:\n",
    "        \"\"\"判断节点i和节点j是否属于同一集合\n",
    "           T: O(α(N) first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        # path compression twice\n",
    "        return self.findSet(i) == self.findSet(j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.par = {}\n",
    "        self.rank = {}\n",
    "\n",
    "    def find(self, n):\n",
    "        p = self.par[n]\n",
    "        while p!= self.par[p]:\n",
    "            self.par[p] = self.par[self.par[p]]\n",
    "            p = self.par[p]\n",
    "        return p\n",
    "\n",
    "    def union(self, n1, n2):\n",
    "        p1, p2 = self.find(n1), self.find(n2)\n",
    "        if p1 == p2:\n",
    "            return False\n",
    "        if self.rank[p1] < self.rank[p2]:\n",
    "            self.par[p1] = p2\n",
    "            self.rank[p2] += self.rank[p1]\n",
    "        else:\n",
    "            self.par[p2] = p1\n",
    "            self.rank[p1] += self.rank[p2]\n",
    "\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        n = len(accounts)\n",
    "        email2acc = {}\n",
    "\n",
    "        for i in range(n):\n",
    "            self.par[i] = i\n",
    "            self.rank[i] = 1\n",
    "\n",
    "        for i, acc in enumerate(accounts):\n",
    "            for email in acc[1:]:\n",
    "                if email in email2acc:\n",
    "                    self.union(i, email2acc[email])\n",
    "                else:\n",
    "                    email2acc[email] = i\n",
    "        \n",
    "        email_group = defaultdict(list)\n",
    "        for email, acc in email2acc.items():\n",
    "            p = self.find(acc)\n",
    "            email_group[p].append(email)\n",
    "        \n",
    "        res = []\n",
    "        for acc, emails in email_group.items():\n",
    "            acc_emails = [accounts[acc][0]] + sorted(emails)\n",
    "            res.append(acc_emails)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 这个题算是数据处理，很适合于python。\n",
    "    # 简而言之，python适合【快速编程】与【多变需求】，而\n",
    "    # c++适合【高优化编程】与【高复用需求】。\n",
    "    # \n",
    "    # 这个题根本上是一个nosql的数据库问题。既然nosql也就用不着pandas，写吧。\n",
    "    # 这个题是一个合并merging题，所以我们做并查集。\n",
    "    # \n",
    "    # 【并查集】就适合于【等价类】的区分，即：\n",
    "    # 一些“样本点”会被（按照一些特征）映射到不同的集合中，这些集合互不相交，且集合内部满足相同的性质。若ab,bc属于同一集合，则ac必然属于同一集合。能够造成多个 样本点 的【等价】。\n",
    "    # 【并查集】的好处就是，【一遍遍历，就成功分类】。\n",
    "\n",
    "    # 本题算法：并查集根据“邮箱”建立。\n",
    "    # 1 我们为每个邮箱维护一个 人名。\n",
    "    # 2 我们将每个账户中的所有邮箱进行一次union操作；这样的话，同一个邮箱所在的两个账户必然会被合并了。\n",
    "    # 我们就先省略“按秩合并”，那是一个比较鸡肋的东西。我们仅仅路径压缩。\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        email_list = []\n",
    "        email2idx = {}\n",
    "        email2name = {}\n",
    "        cnt = 0\n",
    "        for account in accounts:\n",
    "            name = account[0]\n",
    "            for email in account[1:]:\n",
    "                if email not in email2idx:\n",
    "                    email_list.append(email)\n",
    "                    email2name[email] = name\n",
    "                    email2idx[email] = cnt\n",
    "                    cnt += 1\n",
    "        n = len(email_list)\n",
    "        # 合并\n",
    "        unionFindSet = UnionFindSet(n) # 我们的并查集\n",
    "        for account in accounts:\n",
    "            name = account[0]\n",
    "            first_email_idx = email2idx[account[1]]\n",
    "            for email in account[2:]:\n",
    "                unionFindSet.union(first_email_idx, email2idx[email])\n",
    "        # 遍历合并后的并查集，根据序号得到人名归属\n",
    "        res_hash = {}\n",
    "        for i in range(n):\n",
    "            root = unionFindSet.find(i)\n",
    "            if root not in res_hash:\n",
    "                res_hash[root] = []\n",
    "            res_hash[root].append(email_list[i])\n",
    "        res = []\n",
    "        for k, v in res_hash.items():\n",
    "            v = sorted(v)\n",
    "            res.append([email2name[email_list[k]]] + v)\n",
    "        return res\n",
    "            \n",
    "\n",
    "class UnionFindSet: # 我要写一个并查集类模板\n",
    "    # 包含：基本模式；路径压缩.\n",
    "    # 并查集核心两个函数：find, union(merge)\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "\n",
    "    def find(self, idx):\n",
    "        if self.parent[idx] != idx:\n",
    "            self.parent[idx] = self.find(self.parent[idx])\n",
    "        return self.parent[idx]\n",
    "\n",
    "    def union(self, idx1, idx2):\n",
    "        self.parent[self.find(idx1)] = self.find(idx2)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.p = [i for i in range(n + 1)]\n",
    "        self.sz = [1 for i in range(n + 1)]\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.p[x] != x:\n",
    "            self.p[x] = self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        px, py = self.find(x), self.find(y)\n",
    "        if px == py:\n",
    "            return\n",
    "        self.p[px] = py\n",
    "        self.sz[py] += self.sz[px]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        email_to_index = dict()\n",
    "        email_to_name = dict()\n",
    "        for account in accounts:\n",
    "            name = account[0]\n",
    "            for email in account[1:]:\n",
    "                if email not in email_to_index:\n",
    "                    email_to_index[email] = len(email_to_index)\n",
    "                    email_to_name[email] = name\n",
    "        dsu = DSU(len(email_to_index))\n",
    "        for account in accounts:\n",
    "            first_email = account[1]\n",
    "            for email in account[2:]:\n",
    "                dsu.union(email_to_index[first_email], email_to_index[email])\n",
    "        index_to_emails = collections.defaultdict(list)\n",
    "        for email, index in email_to_index.items():\n",
    "            index = dsu.find(index)\n",
    "            index_to_emails[index].append(email)\n",
    "        ans = []\n",
    "        for emails in index_to_emails.values():\n",
    "            ans.append([email_to_name[emails[0]]] + sorted(emails))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.p = [i for i in range(n + 1)]\n",
    "        self.sz = [1 for i in range(n + 1)]\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.p[x] != x:\n",
    "            self.p[x] = self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        px, py = self.find(x), self.find(y)\n",
    "        if px == py:\n",
    "            return\n",
    "        self.p[px] = py\n",
    "        self.sz[py] += self.sz[px]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        email_to_index = dict()\n",
    "        email_to_name = dict()\n",
    "        for account in accounts:\n",
    "            name = account[0]\n",
    "            for email in account[1:]:\n",
    "                if email not in email_to_index:\n",
    "                    email_to_index[email] = len(email_to_index)\n",
    "                    email_to_name[email] = name\n",
    "        dsu = DSU(len(email_to_index))\n",
    "        for account in accounts:\n",
    "            first_email = account[1]\n",
    "            for email in account[2:]:\n",
    "                dsu.union(email_to_index[first_email], email_to_index[email])\n",
    "        index_to_emails = collections.defaultdict(list)\n",
    "        for email, index in email_to_index.items():\n",
    "            index = dsu.find(index)\n",
    "            index_to_emails[index].append(email)\n",
    "        ans = []\n",
    "        for emails in index_to_emails.values():\n",
    "            ans.append([email_to_name[emails[0]]] + sorted(emails))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#定义并查集\n",
    "class Unionset:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "\t#将index1的根作为index2的根\n",
    "    def union(self, index1: int, index2: int):\n",
    "        self.parent[self.find(index2)] = self.find(index1)\n",
    "\t#找到index的根，根的判别依据为父节点是自身\n",
    "    def find(self, index: int) -> int:\n",
    "        if self.parent[index] != index:\n",
    "            self.parent[index] = self.find(self.parent[index])\n",
    "        return self.parent[index]\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        emailToIndex = dict()\n",
    "        emailToName = dict()\n",
    "\t\t#对两个字典进行初始化\n",
    "        for account in accounts:\n",
    "            Name = account[0]\n",
    "            for email in account[1:]:\n",
    "                if email not in emailToIndex:\n",
    "                    emailToName[email] = Name\n",
    "                    emailToIndex[email] = len(emailToIndex)\n",
    "        ufs = Unionset(len(emailToIndex))\n",
    "\t\t#先将已知为一个账户拥有的邮箱通过并查集进行合并\n",
    "        for account in accounts:\n",
    "            firstIndex = emailToIndex[account[1]]\n",
    "            for email in account[2:]:\n",
    "                ufs.union(firstIndex, emailToIndex[email])\n",
    "        #将根节点为相同节点的邮箱进行合并，最终项数的即为不同账户的个数\n",
    "        indexToEmails = collections.defaultdict(list)\n",
    "        for email, index in emailToIndex.items():\n",
    "            index = ufs.find(index)\n",
    "            indexToEmails[index].append(email)\n",
    "        #选取首部邮箱的账户名作为最终账户名，并对邮箱按ASKII顺序排序，得到最终结果\n",
    "        answer = list()\n",
    "        for emails in indexToEmails.values():\n",
    "            answer.append([emailToName[emails[0]]] + sorted(emails))\n",
    "        \n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        email_2_name = {}\n",
    "        adj_list = defaultdict(list)\n",
    "\n",
    "        for acc in accounts:\n",
    "            name, e0, rem = acc[0], acc[1], acc[2:]\n",
    "            email_2_name[e0] = name\n",
    "            for tmp in rem:\n",
    "                adj_list[e0].append(tmp)\n",
    "                adj_list[tmp].append(e0)\n",
    "                email_2_name[tmp] = name\n",
    "\n",
    "        visited = set()\n",
    "        queue = deque([])\n",
    "        res = []\n",
    "        # traverse each non-visited email\n",
    "        for email in email_2_name:\n",
    "            if email in visited:    continue\n",
    "            visited.add(email)\n",
    "            queue.append(email)\n",
    "\n",
    "            routes = []\n",
    "            while queue:\n",
    "                cur = queue.popleft()\n",
    "                routes.append(cur)\n",
    "                for nxt in adj_list[cur]:\n",
    "                    if nxt not in visited:\n",
    "                        queue.append(nxt)\n",
    "                        visited.add(nxt)\n",
    "\n",
    "            # push traversed route for connected emails\n",
    "            res.append([email_2_name[email]] + sorted(routes))\n",
    "        \n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        email_to_index_dict = {}\n",
    "        name_list = [\"\"]*len(accounts)\n",
    "        email_set_list = [None]*len(accounts)\n",
    "        data = [i for i in range(len(accounts))]\n",
    "\n",
    "        def find(a):\n",
    "            if data[a]==a:\n",
    "                return a\n",
    "            t = find(data[a])\n",
    "            data[a]  = t\n",
    "            return t\n",
    "        \n",
    "        def union(a,b):\n",
    "            a = find(a)\n",
    "            b = find(b)\n",
    "            data[a] = b\n",
    "            \n",
    "        for index, account in enumerate(accounts):\n",
    "            name ,*emails = account\n",
    "            name_list[index] = name\n",
    "            email_set_list[index] = set(emails)\n",
    "\n",
    "            for email in emails:\n",
    "                t_index = email_to_index_dict.get(email,index )\n",
    "                if t_index != index:\n",
    "                    union(index,t_index)\n",
    "                email_to_index_dict[email] = index\n",
    "        real_data = [set() for _ in range(len(accounts))]\n",
    "        for i, v in enumerate(data):\n",
    "            real_data[find(v)] |=email_set_list[i]\n",
    "        ans = []\n",
    "        for i in range(len(accounts)):\n",
    "            if v:= real_data[i]:\n",
    "                ans.append([name_list[i]]+sorted(v))\n",
    "        return ans\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parents = [i for i in range(n)]\n",
    "\n",
    "    def union(self, account1, account2):\n",
    "        self.parents[self.find(account1)] = self.find(account2)\n",
    "    \n",
    "    def find(self, account):\n",
    "        if self.parents[account] != account:\n",
    "            self.parents[account] = self.find(self.parents[account])\n",
    "        return self.parents[account]\n",
    "            \n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        nameAccounts = {}\n",
    "        for account in accounts:\n",
    "            name = account[0]\n",
    "            if name not in nameAccounts:\n",
    "                nameAccounts[name] = []\n",
    "            nameAccounts[name].append(account)\n",
    "        \n",
    "        results = []\n",
    "        for name in nameAccounts:\n",
    "            curAccounts = nameAccounts[name]\n",
    "            accountIds = {}\n",
    "            for accountList in curAccounts:\n",
    "                for idx in range(1, len(accountList)):\n",
    "                    if accountList[idx] not in accountIds:\n",
    "                        accountIds[accountList[idx]] = len(accountIds)\n",
    "            \n",
    "            unionFind = UnionFind(len(accountIds))\n",
    "            for accountList in curAccounts:\n",
    "                firstAccount = accountList[1]\n",
    "                firstAccountId = accountIds[accountList[1]]\n",
    "                for idx in range(2, len(accountList)):\n",
    "                    accountId = accountIds[accountList[idx]]\n",
    "                    unionFind.union(firstAccountId, accountId)\n",
    "            \n",
    "            mergedAccounts = {}\n",
    "            for accountList in curAccounts:\n",
    "                for idx in range(1, len(accountList)):\n",
    "                    accountId = accountIds[accountList[idx]]\n",
    "                    tmpId = unionFind.find(accountId)\n",
    "                    if tmpId not in mergedAccounts:\n",
    "                        mergedAccounts[tmpId] = set()\n",
    "                    mergedAccounts[tmpId].add(accountList[idx])\n",
    "            for key in mergedAccounts:\n",
    "                mergedAccounts[key] = list(mergedAccounts[key])\n",
    "                mergedAccounts[key].sort()\n",
    "                results.append([name] + mergedAccounts[key])\n",
    "        \n",
    "        return results\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "    \n",
    "    def find(self, i):\n",
    "        while (self.parent[i] != i):\n",
    "            i, self.parent[i] = self.parent[i], self.parent[self.parent[i]]\n",
    "        return i \n",
    "\n",
    "    def union(self, i, j):\n",
    "        pi = self.find(i)\n",
    "        pj = self.find(j)\n",
    "        if pi == pj:\n",
    "            return \n",
    "        if self.size[pi] > self.size[pj]:\n",
    "            self.parent[pj] = pi \n",
    "            self.size[pi] += 1 \n",
    "        else: \n",
    "            self.parent[pi] = pj \n",
    "            self.size[pj] += 1\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        email2idx = {}\n",
    "        n = len(accounts)\n",
    "        uf = UF(n)\n",
    "        for i, val in enumerate(accounts):\n",
    "            emails = val[1:]\n",
    "            for e in emails:\n",
    "                if e in email2idx:\n",
    "                    # merge\n",
    "                    uf.union(email2idx[e], i)\n",
    "                else:\n",
    "                    email2idx[e] = i \n",
    "        \n",
    "        # after merge:\n",
    "        # return a list of indices \n",
    "        idx2email = defaultdict(set)\n",
    "        for i, account in enumerate(accounts):\n",
    "            parent = uf.find(i)\n",
    "            idx2email[parent].update(account[1:])\n",
    "        \n",
    "        res = []\n",
    "        for key, val in idx2email.items():\n",
    "            account = [accounts[key][0]]\n",
    "            val = sorted(val)\n",
    "            account.extend(val)\n",
    "            res.append(account)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\" \n",
    "Question: combine accounts that have the same email, return them in a list of name and emails(asc)\n",
    "input: account [[name, emails...]]\n",
    "reutrn: [[name, emails asc]]\n",
    "constraints:\n",
    "- there are at least 1 account\n",
    "- there are at least 1 email in each account\n",
    "------------------------------\n",
    "store every email as their own root\n",
    "go through accounts, union email\n",
    "name:\n",
    "\"\"\"\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        \"\"\" initialize each eamil as a distinct set \"\"\"\n",
    "        # label email from 0\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.rank = [0] * n\n",
    "        self.set_count = n\n",
    "\n",
    "    def find(self, num) -> int:\n",
    "        \"\"\" return the root parent of num, compress path \"\"\"\n",
    "        if self.parent[num] != num:\n",
    "            self.parent[num] = self.find(self.parent[num])\n",
    "        return self.parent[num]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rootx = self.find(x)\n",
    "        rooty = self.find(y)\n",
    "\n",
    "        # need union\n",
    "        if rootx != rooty:\n",
    "            if self.rank[rootx] < self.rank[rooty]:\n",
    "                rootx, rooty = rooty, rootx\n",
    "            # attach rooty(shorter) to rootx(higher)\n",
    "            self.parent[rooty] = rootx\n",
    "            if self.rank[rooty] == self.rank[rootx]:\n",
    "                self.rank[rootx] += 1\n",
    "            self.set_count -= 1\n",
    "\n",
    "    def is_connected(self, x, y) -> bool:\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        # label every email to a distinct number\n",
    "        # record owner's name of each email\n",
    "        email_num = {}\n",
    "        email_name = {}\n",
    "        for account in accounts:\n",
    "            for email in account[1:]:\n",
    "                if email not in email_num:\n",
    "                    email_num[email] = len(email_num)\n",
    "                    email_name[email] = account[0]\n",
    "        \n",
    "        uf = UnionFind(len(email_num))\n",
    "        # union all emails in the same account\n",
    "        for account in accounts:\n",
    "            first_num = email_num[account[1]]\n",
    "            for other_num in account[2:]:\n",
    "                uf.union(first_num, email_num[other_num])\n",
    "\n",
    "        # group emails by their root\n",
    "        root_email = collections.defaultdict(list)\n",
    "        for email, num in email_num.items():\n",
    "            root = uf.find(num)\n",
    "            root_email[root].append(email)\n",
    "        \n",
    "        ans = []\n",
    "        for emails in root_email.values():\n",
    "            ans.append([email_name[emails[0]]] + sorted(emails))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        class UF():\n",
    "            def __init__(self,n):\n",
    "                self.parent = list(range(n))\n",
    "                \n",
    "            def find(self,idx):\n",
    "                if self.parent[idx] != idx:\n",
    "                    self.parent[idx] = self.find(self.parent[idx])\n",
    "                return(self.parent[idx])\n",
    "            \n",
    "            def union(self,idx1,idx2):\n",
    "                root_idx1 = self.find(idx1)\n",
    "                root_idx2 = self.find(idx2)\n",
    "                self.parent[root_idx1] = root_idx2\n",
    "\n",
    "        # 邮箱 变成 编码\n",
    "        # 编码 记录 用户，一个编码也就是邮箱，不可能有两个用户\n",
    "        # 还得记录一个 编码转 邮箱的，因为最后答案得写成 邮箱\n",
    "        idx = 0\n",
    "        email_to_idx = {} \n",
    "        idx_to_user = {}  \n",
    "        for account in accounts:\n",
    "            user,emails = account[0],account[1:]\n",
    "            for email in emails:\n",
    "                if email not in email_to_idx:\n",
    "                    email_to_idx[email] = idx\n",
    "                    idx_to_user[idx] = user\n",
    "                    idx += 1\n",
    "        # display('email_to_idx',email_to_idx)\n",
    "        # display('idx_to_user',idx_to_user)\n",
    "\n",
    "        idx_to_email = {email_to_idx[k]:k for k in email_to_idx}\n",
    "\n",
    "        uf = UF(len(email_to_idx))\n",
    "        for account in accounts:\n",
    "            user,emails = account[0],account[1:]\n",
    "            email_1 = emails[0]\n",
    "            idx_1 = email_to_idx[email_1]\n",
    "            for email_2 in emails[1:]:\n",
    "                idx_2 = email_to_idx[email_2]\n",
    "                uf.union(idx_1,idx_2)\n",
    "                \n",
    "        # 收集每个邮箱 相关的邮箱，也就是 根据 一个 根节点 邮箱，收集全部 下属邮箱\n",
    "        # 不要对 accounts 循环，因为这里面有冗余的，对 字典循环\n",
    "        root_email_dic = collections.defaultdict(list)\n",
    "        for idx  in idx_to_email:\n",
    "            root_idx = uf.find(idx)\n",
    "            root_email_dic[root_idx].append(idx)\n",
    "\n",
    "        # 再根据 根节点 邮箱 找到 user\n",
    "        res = []\n",
    "        for root_idx in root_email_dic:\n",
    "            user = idx_to_user[root_idx]\n",
    "            idxs = root_email_dic[root_idx]\n",
    "            emails = [idx_to_email[idx] for idx in idxs]\n",
    "            res.append([user]+sorted(emails))\n",
    "        return(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.parent = {}\n",
    "    def union(self, index1: int, index2: int):\n",
    "        self.parent[self.find(index2)] = self.find(index1)\n",
    "    def find(self, index: int) -> int:\n",
    "        self.parent.setdefault(index,index)\n",
    "        if self.parent[index] != index:\n",
    "            self.parent[index] = self.find(self.parent[index])\n",
    "        return self.parent[index]\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        emailToName = dict()\n",
    "        for account in accounts:\n",
    "            for email in account[1:]:\n",
    "                emailToName[email] = account[0]\n",
    "        uf = UnionFind()\n",
    "        for account in accounts:\n",
    "            for email in account[2:]:\n",
    "                uf.union(account[1], email)\n",
    "        indexToEmails = collections.defaultdict(set)\n",
    "        for account in accounts:\n",
    "            for email in account[1:]:\n",
    "                f = uf.find(email)\n",
    "                indexToEmails[f].add(email)\n",
    "                # indexToEmails[f].add(f)\n",
    "        ans = list()\n",
    "        for k,v in indexToEmails.items():\n",
    "            ans.append([emailToName[k]] + sorted(v))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        email_2_name = {}\n",
    "        adj_list = defaultdict(list)\n",
    "\n",
    "        for acc in accounts:\n",
    "            name, e0, rem = acc[0], acc[1], acc[2:]\n",
    "            email_2_name[e0] = name\n",
    "            for tmp in rem:\n",
    "                adj_list[e0].append(tmp)\n",
    "                adj_list[tmp].append(e0)\n",
    "                email_2_name[tmp] = name\n",
    "\n",
    "        visited = set()\n",
    "        queue = deque([])\n",
    "        res = []\n",
    "        for email in email_2_name:\n",
    "            if email in visited:    continue\n",
    "            visited.add(email)\n",
    "            queue.append(email)\n",
    "\n",
    "            routes = []\n",
    "            while queue:\n",
    "                cur = queue.popleft()\n",
    "                routes.append(cur)\n",
    "                for nxt in adj_list[cur]:\n",
    "                    if nxt not in visited:\n",
    "                        queue.append(nxt)\n",
    "                        visited.add(nxt)\n",
    "\n",
    "            res.append([email_2_name[email]] + sorted(routes))\n",
    "        \n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        d=dict()\n",
    "        fa=dict()\n",
    "        def find(x):\n",
    "            if x not in fa:\n",
    "                fa[x]=x\n",
    "            elif fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(a,b):\n",
    "            if find(a)!=find(b):\n",
    "                fa[find(a)]=find(b)\n",
    "        for ac in accounts:\n",
    "            m=len(ac)\n",
    "            if m==2:\n",
    "                find(ac[1])\n",
    "                d[ac[1]]=ac[0]\n",
    "            else:\n",
    "                for i in range(1,m):\n",
    "                    d[ac[i]]=ac[0]\n",
    "                    for j in range(i+1,m):\n",
    "                        union(ac[i],ac[j])\n",
    "        ret=[]\n",
    "        e=collections.defaultdict(list)\n",
    "        for key in fa:\n",
    "            e[find(key)].append(key)\n",
    "        print(fa,e)\n",
    "        for key in e:\n",
    "            ls=[d[e[key][0]]]\n",
    "            e[key].sort()\n",
    "            ls+=e[key]\n",
    "            ret.append(copy.deepcopy(ls))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        # 构建无向图，每个邮箱为一个节点，同一个账户的邮箱全部相连\n",
    "        # 有多少连通分量，就有多少独立的账户\n",
    "        # 该字典，键为一个邮箱，值为与其相连的所有邮箱\n",
    "        graph = collections.defaultdict(list)\n",
    "        for account in accounts:\n",
    "            master = account[1]\n",
    "            for email in list(set(account[2:])):\n",
    "                graph[master].append(email)\n",
    "                graph[email].append(master)\n",
    "\n",
    "        res = [] # 最终的输出结果\n",
    "        visited = set() # 标记集合\n",
    "\n",
    "        for account in accounts:\n",
    "            emails = [] # 存储该账户的所有邮箱\n",
    "            # 深度优先遍历\n",
    "            self.dfs(account[1],graph,visited,emails)\n",
    "            if emails:\n",
    "                res.append([account[0]] + sorted(emails))\n",
    "        return res\n",
    "\n",
    "    # 深度优先遍历\n",
    "    def dfs(self,email,graph,visited,emails):\n",
    "        # 访问过，不在添加直接结束\n",
    "        if email in visited:\n",
    "            return \n",
    "        visited.add(email) # 标记访问\n",
    "        emails.append(email) # 添加\n",
    "        for neighbor in graph[email]:\n",
    "            self.dfs(neighbor,graph,visited,emails)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def build_graph(self,accounts):\n",
    "        \"\"\"\n",
    "        建图\n",
    "        \"\"\"\n",
    "        graph = collections.defaultdict(list)\n",
    "        for account in accounts:\n",
    "            name = account[1]\n",
    "            # 对剩余账户做一个去重\n",
    "            for email in account[2:]:\n",
    "                graph[name].append(email)\n",
    "                graph[email].append(name)\n",
    "        \n",
    "        return graph\n",
    "    \n",
    "    def dfs(self,email,graph,visited,emails):\n",
    "        # 已经访问过的就剪枝\n",
    "        if email in visited:\n",
    "            return \n",
    "        visited.add(email)\n",
    "        emails.append(email)\n",
    "        # 对邻居节点继续深搜\n",
    "        for neighbor in graph[email]:\n",
    "            self.dfs(neighbor,graph,visited,emails)\n",
    "    \n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        graph = self.build_graph(accounts)\n",
    "\n",
    "        res = []\n",
    "        visited = set()\n",
    "        for account in accounts:\n",
    "            emails = []\n",
    "            self.dfs(account[1],graph,visited,emails) # 每一条记录的第一个邮箱为起始点\n",
    "            if emails:\n",
    "                res.append([account[0]] + sorted(emails))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def build_graph(self,accounts):\n",
    "        \"\"\"\n",
    "        建图\n",
    "        \"\"\"\n",
    "        graph = collections.defaultdict(list)\n",
    "        for account in accounts:\n",
    "            master = account[1]\n",
    "            # 对剩余账户做一个去重\n",
    "            for email in list(set(account[2:])):\n",
    "                graph[master].append(email)\n",
    "                graph[email].append(master)\n",
    "        \n",
    "        return graph\n",
    "    \n",
    "    def dfs(self,email,graph,visited,emails):\n",
    "        \"\"\"\n",
    "        深搜遍历\n",
    "        \"\"\"\n",
    "        # 已经访问过的就剪枝\n",
    "        if email in visited:\n",
    "            return \n",
    "        \n",
    "        visited.add(email)\n",
    "        emails.append(email)\n",
    "        \n",
    "        # 对邻居节点继续深搜\n",
    "        for neighbor in graph[email]:\n",
    "            self.dfs(neighbor,graph,visited,emails)\n",
    "    \n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        graph = self.build_graph(accounts)\n",
    "\n",
    "        res = []\n",
    "        visited = set()\n",
    "        for account in accounts:\n",
    "            emails = []\n",
    "            self.dfs(account[1],graph,visited,emails)\n",
    "            if emails:\n",
    "                res.append([account[0]] + sorted(emails))\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        # 构建无向图，每个邮箱为一个节点，同一个账户的邮箱全部相连\n",
    "        # 有多少连通分量，就有多少独立的账户\n",
    "        # 该字典，键为一个邮箱，值为与其相连的所有邮箱\n",
    "        graph = collections.defaultdict(list)\n",
    "        for account in accounts:\n",
    "            master = account[1]\n",
    "            for email in list(set(account[2:])):\n",
    "                graph[master].append(email)\n",
    "                graph[email].append(master)\n",
    "\n",
    "        res = [] # 最终的输出结果\n",
    "        visited = set() # 标记集合\n",
    "\n",
    "        for account in accounts:\n",
    "            emails = [] # 存储该账户的所有邮箱\n",
    "            # 深度优先遍历\n",
    "            self.dfs(account[1],graph,visited,emails)\n",
    "            if emails:\n",
    "                res.append([account[0]] + sorted(emails))\n",
    "        return res\n",
    "\n",
    "    # 深度优先遍历\n",
    "    def dfs(self,email,graph,visited,emails):\n",
    "        # 访问过，不在添加直接结束\n",
    "        if email in visited:\n",
    "            return \n",
    "        visited.add(email) # 标记访问\n",
    "        emails.append(email) # 添加\n",
    "        for neighbor in graph[email]:\n",
    "            self.dfs(neighbor,graph,visited,emails)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        #去除重复\n",
    "        new_acconuts = []\n",
    "        for i in range(len(accounts)):\n",
    "            tmp = []\n",
    "            for j in range(len(accounts[i])):\n",
    "                if accounts[i][j] not in tmp:\n",
    "                    tmp.append(accounts[i][j])\n",
    "            new_acconuts.append(tmp)\n",
    "        accounts = new_acconuts\n",
    "        #创建出现过的所有邮箱的列表，他们出现在哪些账号里\n",
    "        mail_set = {}\n",
    "        for i in range(len(accounts)):\n",
    "            for j in range(1,len(accounts[i])):\n",
    "                if accounts[i][j] not in mail_set:\n",
    "                    mail_set[accounts[i][j]] = [i]\n",
    "                else:\n",
    "                    mail_set[accounts[i][j]].append(i)\n",
    "        print(mail_set)\n",
    "\n",
    "        #先把set里面的东西给\n",
    "        ans = []#记录合并后的账号\n",
    "        for i in mail_set:\n",
    "            ans.append(mail_set[i])\n",
    "        \n",
    "        #合并\n",
    "        for i in range(len(accounts)):\n",
    "            tmp = []\n",
    "            for k in range(len(ans)):\n",
    "                if i in ans[k]:\n",
    "                    tmp.append(k)\n",
    "            \n",
    "            res = []\n",
    "            for j in range(len(tmp)):\n",
    "                for k in range(len(ans[tmp[j]])):\n",
    "                    if ans[tmp[j]][k] not in res:\n",
    "                        res.append(ans[tmp[j]][k])\n",
    "            \n",
    "            for j in tmp:\n",
    "                ans[j] = []\n",
    "            # ans = [ans[i] for i in range(len(ans)) if i not in tmp]\n",
    "            ans.append(res)\n",
    "        ans = [i for i in ans if i]\n",
    "        # print(ans)\n",
    "        #互不相干的直接装进去\n",
    "        res = []\n",
    "        for it in ans:\n",
    "            if len(it) == 1:\n",
    "                tmp = accounts[it[0]][1:]\n",
    "                tmp = sorted(tmp)\n",
    "                tmp.insert(0, accounts[it[0]][0])\n",
    "                res.append(tmp)\n",
    "            else:\n",
    "                #合并,先把名称放进去\n",
    "                tmp = []\n",
    "                for j in range(len(it)):\n",
    "                    for k in range(1,len(accounts[it[j]])):\n",
    "                        if accounts[it[j]][k] not in tmp:\n",
    "                            tmp.append(accounts[it[j]][k])\n",
    "                tmp = sorted(tmp)\n",
    "                tmp.insert(0, accounts[it[0]][0])\n",
    "                res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        for acc in accounts:\n",
    "            holder = acc[1]\n",
    "            for email in list(set(acc[2:])):\n",
    "                graph[holder].append(email)\n",
    "                graph[email].append(holder)\n",
    "\n",
    "\n",
    "        def dfs(email,graph,visited,emails):\n",
    "            if email in visited:\n",
    "                return\n",
    "\n",
    "            visited.add(email)\n",
    "            emails.append(email)\n",
    "\n",
    "            for neighbor in graph[email]:\n",
    "                dfs(neighbor,graph,visited,emails)\n",
    "        \n",
    "        ans = []\n",
    "        visited = set()\n",
    "        for acc in accounts:\n",
    "            emails = []\n",
    "            dfs(acc[1],graph,visited,emails)\n",
    "            if emails:\n",
    "                ans.append([acc[0]] + sorted(emails))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        class UnionFind:\n",
    "            def __init__(self, n):\n",
    "                self.parents = dict()\n",
    "                for i in range(n):\n",
    "                    self.parents[i] = i\n",
    "\n",
    "            def find(self, x):\n",
    "                if self.parents[x]!=x:\n",
    "                    return self.find(self.parents[x])\n",
    "                else:\n",
    "                    return x\n",
    "\n",
    "            def union(self, a, b):\n",
    "                self.parents[self.find(a)] = self.find(b)\n",
    "        \n",
    "        from collections import defaultdict\n",
    "        rela = defaultdict(list)\n",
    "        for i in range(len(accounts)):\n",
    "            for email in accounts[i][1:]:\n",
    "                rela[email].append(i)\n",
    "        \n",
    "        uf = UnionFind(len(accounts))\n",
    "        for r in rela:\n",
    "            if len(rela[r])>1:\n",
    "                for node in rela[r][1:]:\n",
    "                    uf.union(rela[r][0], node)\n",
    "        print(uf.parents)\n",
    "\n",
    "        index_emails = defaultdict(set)\n",
    "        for i in range(len(accounts)):\n",
    "            for email in accounts[i][1:]:\n",
    "                index_emails[uf.find(i)].add(email)\n",
    "        print(index_emails)\n",
    "\n",
    "        ans = []\n",
    "        for i in index_emails:\n",
    "            curr = [accounts[i][0]] + sorted(index_emails[i])\n",
    "            ans.append(curr)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet:\n",
    "    def __init__(self, emails: List[str]) -> None:\n",
    "        self.parent = defaultdict(str)\n",
    "        for email in emails:\n",
    "            self.parent[email] = email\n",
    "        self.rank = defaultdict(int)\n",
    "        \n",
    "    def find(self, x: str) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "        \n",
    "    def union(self, x: str, y: str) -> None:\n",
    "        xroot, yroot = self.find(x), self.find(y)\n",
    "        if xroot != yroot:\n",
    "            if self.rank[xroot] < self.rank[yroot]:\n",
    "                xroot, yroot = yroot, xroot\n",
    "            self.parent[yroot] = xroot\n",
    "            if self.rank[xroot] == self.rank[yroot]:\n",
    "                self.rank[xroot] += 1\n",
    "                \n",
    "    def is_connected(self, x: str, y: str) -> bool:\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "\n",
    "        email2name = defaultdict(str)\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        for account in accounts:\n",
    "            name, emails = account[0], account[1:]\n",
    "            m = len(emails)\n",
    "            for i in range(m):\n",
    "                u = emails[i]\n",
    "                email2name[u] = name\n",
    "                for j in range(i + 1, m):\n",
    "                    v = emails[j]\n",
    "                    graph[u].append(v)\n",
    "                    graph[v].append(u)\n",
    "\n",
    "        ufs = UnionFindSet(list(email2name.keys()))\n",
    "\n",
    "        for u, adju in graph.items():\n",
    "            for v in adju:\n",
    "                ufs.union(u, v)\n",
    "\n",
    "        components = defaultdict(list)\n",
    "        for email in email2name.keys():\n",
    "            components[ufs.find(email)].append(email)\n",
    "\n",
    "        res = []\n",
    "        for root, component in components.items():\n",
    "            res.append([email2name[root]] + sorted(component))\n",
    "\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "\n",
    "\n",
    "        def isSameaccount(a1, a2):\n",
    "            if a1[0] != a2[0]: return False\n",
    "            for i in range(1, len(a1)):\n",
    "                for j in range(1, len(a2)):\n",
    "                    if a1[i] == a2[j]: return True\n",
    "            return False\n",
    "        \n",
    "        def buildGraph(accounts):\n",
    "            n = len(accounts)\n",
    "            graph = [[] for _ in range(n)]\n",
    "\n",
    "            for i in range(n):\n",
    "                for j in range(i+1, n):\n",
    "                    if isSameaccount(accounts[i], accounts[j]):\n",
    "                        graph[i].append(j)\n",
    "                        graph[j].append(i)\n",
    "            return graph\n",
    "\n",
    "        graph = buildGraph(accounts)\n",
    "        \n",
    "        def dfs(i, seen, graph, curr):\n",
    "            if seen[i]: return\n",
    "            seen[i] = 1\n",
    "            for email in accounts[i][1:]:\n",
    "                curr.add(email)\n",
    "            \n",
    "            for nei in graph[i]:\n",
    "                dfs(nei, seen, graph, curr)\n",
    "        \n",
    "        ans = []\n",
    "        seen = [0]*len(accounts)\n",
    "        for i in range(len(accounts)):\n",
    "            if seen[i]: continue\n",
    "            curr = set()\n",
    "            dfs(i, seen, graph, curr)\n",
    "            ans.append([accounts[i][0]]+sorted(list(curr)))\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DS:\n",
    "    def __init__(self, n):\n",
    "        self.rec = [i for i in range(n)]\n",
    "        \n",
    "    def union(self, x, y):\n",
    "        ux = self.find(x)\n",
    "        uy = self.find(y)\n",
    "        if ux != uy:\n",
    "            self.rec[self.find(y)] = x\n",
    "            \n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.rec[x] != x:\n",
    "            x = self.find(self.rec[x])\n",
    "        return x\n",
    "    \n",
    "class Solution:\n",
    "    def mail2id(self, accounts):\n",
    "        m2i = {}\n",
    "        i2m = {}\n",
    "        i2n = {}\n",
    "        idx = 0\n",
    "        for account in accounts:\n",
    "            name = account[0]\n",
    "            mails = account[1:]\n",
    "            mails = list(set(mails))\n",
    "            for mail in mails:\n",
    "                if mail not in m2i:\n",
    "                    m2i[mail] = idx\n",
    "                    i2m[idx] = mail\n",
    "                    i2n[idx] = name\n",
    "                    idx += 1\n",
    "        return idx, m2i, i2m, i2n\n",
    "        \n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        n, m2i, i2m, i2n = self.mail2id(accounts)\n",
    "        ds = DS(n)\n",
    "        for account in accounts:\n",
    "            mails = account[1:]\n",
    "            mails = list(set(mails))\n",
    "            for i in range(len(mails)-1):\n",
    "                id1 = m2i[mails[i]]\n",
    "                id2 = m2i[mails[i+1]]\n",
    "                ds.union(id1, id2)\n",
    "        res = {}\n",
    "        rec = ds.rec\n",
    "        for i in range(n):\n",
    "            root = ds.find(i)\n",
    "            name = i2n[i]\n",
    "            mail = i2m[i]\n",
    "            res.setdefault(root,  [name]).append(mail)\n",
    "        for k in res:\n",
    "            res[k] = [res[k][0]] + sorted(res[k][1:])\n",
    "        return [res[k] for k in res]\n",
    "        \n",
    "        \n",
    "\n",
    "            \n",
    "\t\t\t\t\n",
    "                \n",
    "\t\t\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        email2index = {}\n",
    "        email2name = {}\n",
    "        for account in accounts:\n",
    "            name = account[0]\n",
    "            for email in account[1:]:\n",
    "                if email not in email2index:\n",
    "                    email2index[email] = len(email2index)\n",
    "                    email2name[email] = name\n",
    "        \n",
    "        values = [i for i in range(len(email2index))]\n",
    "        uf = UnionFindSet(values)\n",
    "        for account in accounts:\n",
    "            first = email2index[account[1]]\n",
    "            for email in account[2:]:\n",
    "                uf.union(first, email2index[email])\n",
    "        \n",
    "        index2emails = collections.defaultdict(list)\n",
    "        for email, index in email2index.items():\n",
    "            father = uf.find_father(index)\n",
    "            index2emails[father].append(email)\n",
    "\n",
    "        ans = list()\n",
    "        for email in index2emails.values():\n",
    "            ans.append([email2name[email[0]]] + sorted(email))\n",
    "        return ans\n",
    "\n",
    "class Element:\n",
    "\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "\n",
    "\n",
    "class UnionFindSet:\n",
    "\n",
    "    def __init__(self, values):\n",
    "        self.count = 0 \n",
    "        self.element_map = {}\n",
    "        self.father_map = {}\n",
    "        self.size_map = {}\n",
    "\n",
    "        for value in values:\n",
    "            ele = value\n",
    "            self.element_map[value] = ele\n",
    "            self.father_map[ele] =  ele\n",
    "            self.size_map[ele] = 1\n",
    "\n",
    "    def find_father(self, ele):\n",
    "        stack = []\n",
    "        while ele != self.father_map.get(ele):\n",
    "            stack.append(ele)\n",
    "            ele = self.father_map.get(ele)\n",
    "        while stack:\n",
    "            self.father_map[stack.pop()] = ele\n",
    "        return ele\n",
    "\n",
    "    def union(self, a, b):\n",
    "        a_father = self.find_father(self.element_map.get(a))\n",
    "        b_father = self.find_father(self.element_map.get(b))\n",
    "        if a_father != b_father:\n",
    "            big = a_father if self.size_map[a_father] > self.size_map[b_father] else b_father\n",
    "            small = a_father if self.size_map[a_father] <= self.size_map[b_father] else b_father\n",
    "            self.father_map[small] = big\n",
    "            self.size_map[big] = self.size_map[small] + self.size_map[big]\n",
    "            self.size_map.pop(small)\n",
    "    \n",
    "    def is_same_set(self, a, b):\n",
    "        if self.element_map.get(a) and self.element_map.get(b):\n",
    "            return self.find_father(self.element_map.get(a)) == self.find_father(self.element_map.get(b))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "\n",
    "        emailToName = {}\n",
    "        graphs = defaultdict(set)\n",
    "\n",
    "        for acct in accounts:\n",
    "            name = acct[0]\n",
    "            for email in acct[1:]:\n",
    "                graphs[acct[1]].add(email)\n",
    "                graphs[email].add(acct[1])\n",
    "                emailToName[email] = name\n",
    "        \n",
    "        seen = set()\n",
    "        res = []\n",
    "        for email in graphs:\n",
    "            if email not in seen:\n",
    "                seen.add(email)\n",
    "                stack = [email]\n",
    "                comp = []\n",
    "                while stack:\n",
    "                    e = stack.pop(0)\n",
    "                    comp.append(e)\n",
    "                    for g in graphs[e]:\n",
    "                        if g not in seen:\n",
    "                            seen.add(g)\n",
    "                            stack.append(g)\n",
    "                res.append([emailToName[email]] + sorted(comp))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        parent = {}\n",
    "        def find(p):\n",
    "            if p in parent and p != parent[p]:\n",
    "                return find(parent[p])\n",
    "            return p\n",
    "        def union(p, q):\n",
    "            pp = find(p)\n",
    "            pq = find(q)\n",
    "            parent[pp] = pq\n",
    "        \n",
    "        email_to_name = {}\n",
    "        res = defaultdict(list)\n",
    "    \n",
    "        for account in accounts:\n",
    "            for i in range(1, len(account)):\n",
    "                email_to_name[account[i]] = account[0]\n",
    "                if i < len(account)-1:\n",
    "                    union(account[i], account[i+1])\n",
    "        \n",
    "        for email in email_to_name:\n",
    "            res[find(email)].append(email)\n",
    "    \n",
    "        return [[email_to_name[value[0]]] + sorted(value) for value in res.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        class UnionFind():\n",
    "            def __init__(self, n):\n",
    "                self.parents = []\n",
    "                for i in range(n):\n",
    "                    self.parents.append(i)\n",
    "            \n",
    "            def union(self, a, b):\n",
    "                root_a = self.find(a)\n",
    "                root_b = self.find(b)\n",
    "\n",
    "                self.parents[root_b] = root_a\n",
    "            \n",
    "            def find(self, x):\n",
    "                while self.parents[x] != x:\n",
    "                    x = self.parents[x]\n",
    "                \n",
    "                return x\n",
    "\n",
    "        from collections import defaultdict\n",
    "\n",
    "        email_index_dict = defaultdict(set)\n",
    "\n",
    "        uf = UnionFind(len(accounts))\n",
    "\n",
    "        for index_a in range(len(accounts)):\n",
    "            for email in accounts[index_a][1:]:\n",
    "                for index_b in email_index_dict[email]:\n",
    "                    uf.union(index_a, index_b)\n",
    "                email_index_dict[email].add(index_a)\n",
    "        \n",
    "        index_email_dict = defaultdict(set)\n",
    "\n",
    "        for email in email_index_dict.keys():\n",
    "            index = list(email_index_dict[email])[0]\n",
    "            root_index = uf.find(index)\n",
    "\n",
    "            index_email_dict[root_index].add(email)\n",
    "        \n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for index, emails in index_email_dict.items():\n",
    "            name = accounts[index][0]\n",
    "            ans.append([name]+sorted(emails))\n",
    "        \n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        n = len(accounts)\n",
    "        result = []\n",
    "\n",
    "        G = [[] for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            a = set(accounts[i][1:])\n",
    "            for j in range(i + 1, n):\n",
    "                b = set(accounts[j][1:])\n",
    "                if a & b:\n",
    "                    G[i].append(j)\n",
    "                    G[j].append(i)\n",
    "        used = [0] * n\n",
    "        def dfs(u, s):\n",
    "            nonlocal used\n",
    "            used[u] = True\n",
    "            s |= set(accounts[u][1:])\n",
    "            for v in G[u]:\n",
    "                if used[v]:\n",
    "                    continue\n",
    "                dfs(v, s)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            s = set()\n",
    "            dfs(i, s)\n",
    "            result.append(accounts[i][:1] + sorted(list(s)))\n",
    "        \n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        if accounts==[]:return []\n",
    "        dic={}#dic[邮箱]=accounts中的编号\n",
    "        for i in range(len(accounts)):\n",
    "            for j in range(1,len(accounts[i])):\n",
    "                if accounts[i][j] not in dic:\n",
    "                    dic[accounts[i][j]]={i}\n",
    "                else:\n",
    "                    dic[accounts[i][j]].add(i)\n",
    "        zgd=set()\n",
    "        def dfs(idx):\n",
    "            if idx in zgd:return\n",
    "            zgd.add(idx)\n",
    "            for temp in accounts[idx][1:]:#邮箱\n",
    "                data.add(temp)\n",
    "                for kkk in dic[temp]:#邮箱下有的编号\n",
    "                    dfs(kkk)\n",
    "            return\n",
    "        op=[]\n",
    "        for i in range(len(accounts)):\n",
    "            if i not in zgd:\n",
    "                data=set()\n",
    "                dfs(i)\n",
    "                temp=list(data)\n",
    "                temp.sort()\n",
    "                op.append([accounts[i][0]]+temp)\n",
    "        return op"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        email2Name = dict()\n",
    "        edges = defaultdict(list)\n",
    "\n",
    "        for account in accounts:\n",
    "            for i in range(1, len(account)):\n",
    "                if i + 1 < len(account):\n",
    "                    edges[account[i]].append(account[i + 1])\n",
    "                    edges[account[i + 1]].append(account[i])\n",
    "                email2Name[account[i]] = account[0]\n",
    "\n",
    "        print(edges)\n",
    "        print(email2Name)\n",
    "        res = []\n",
    "        visited = set()\n",
    "\n",
    "        for email in email2Name:\n",
    "            if email in visited:\n",
    "                continue\n",
    "            curGroup = []\n",
    "            self.dfs(email, visited, curGroup, edges)\n",
    "            g = sorted(curGroup)\n",
    "            g.insert(0, email2Name[email])\n",
    "            res.append(g)\n",
    "\n",
    "        return res\n",
    "    def dfs(self, cur, visited, curGroup, edges):\n",
    "        if cur in visited:\n",
    "            return \n",
    "        visited.add(cur)\n",
    "        curGroup.append(cur)\n",
    "        for next_node in edges[cur]:\n",
    "            self.dfs(next_node, visited, curGroup, edges)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "    r = defaultdict(lambda:[])\n",
    "    for a in accounts:\n",
    "      n = a[0]\n",
    "      r[n].append(a[1:])\n",
    "    def grp(aEg):\n",
    "      dat = defaultdict(lambda:[])\n",
    "      r = defaultdict(lambda:False)\n",
    "      all = []\n",
    "      for g in aEg:\n",
    "        l = len(g)\n",
    "        for i in range(l):\n",
    "          a = g[i]\n",
    "          for j in range(i, l):\n",
    "            b = g[j]\n",
    "            dat[a].append(b)\n",
    "            dat[b].append(a)\n",
    "      \n",
    "      def div(aE):\n",
    "        r[aE] = True\n",
    "        ret = {aE}\n",
    "        q = [aE]\n",
    "        while len(q) > 0:\n",
    "          e = q.pop(0)\n",
    "          for re in dat[e]:\n",
    "            if False == r[re]:\n",
    "              r[re] = True\n",
    "              ret.add(re)\n",
    "              q.append(re)\n",
    "        lr = list(ret)\n",
    "        lr.sort()\n",
    "        return lr\n",
    "\n",
    "      ret = []\n",
    "      for g in aEg:\n",
    "        for e in g:\n",
    "          if not r[e]:\n",
    "            ret.append(div(e))\n",
    "      return ret\n",
    "\n",
    "    ret = []\n",
    "    for n, e in r.items():\n",
    "      if len(e) > 1:\n",
    "        for g in grp(e):\n",
    "          ret.append([n] + g)\n",
    "      else:\n",
    "        se = set(e[0])\n",
    "        le = list(se)\n",
    "        le.sort()\n",
    "        ret.append([n] + le)\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "    r = defaultdict(lambda:[])\n",
    "    for a in accounts:\n",
    "      n = a[0]\n",
    "      r[n].append(a[1:])\n",
    "    def grp(aEg):\n",
    "      dat = defaultdict(lambda:[])\n",
    "      r = defaultdict(lambda:False)\n",
    "      all = []\n",
    "      for g in aEg:\n",
    "        l = len(g)\n",
    "        for i in range(l):\n",
    "          a = g[i]\n",
    "          for j in range(i, l):\n",
    "            b = g[j]\n",
    "            dat[a].append(b)\n",
    "            dat[b].append(a)\n",
    "      \n",
    "      def div(aE):\n",
    "        r[aE] = True\n",
    "        ret = {aE}\n",
    "        q = [aE]\n",
    "        while len(q) > 0:\n",
    "          e = q.pop(0)\n",
    "          for re in dat[e]:\n",
    "            if False == r[re]:\n",
    "              r[re] = True\n",
    "              ret.add(re)\n",
    "              q.append(re)\n",
    "        lr = list(ret)\n",
    "        lr.sort()\n",
    "        return lr\n",
    "\n",
    "      ret = []\n",
    "      for g in aEg:\n",
    "        for e in g:\n",
    "          if not r[e]:\n",
    "            ret.append(div(e))\n",
    "      return ret\n",
    "\n",
    "    ret = []\n",
    "    for n, e in r.items():\n",
    "      if len(e) > 1:\n",
    "        for g in grp(e):\n",
    "          ret.append([n] + g)\n",
    "      else:\n",
    "        se = set(e[0])\n",
    "        le = list(se)\n",
    "        le.sort()\n",
    "        ret.append([n] + le)\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:   \n",
    "        ## 广度 优先 搜索 (BFS)\n",
    "                ## 建图\n",
    "        graph = collections.defaultdict(set)\n",
    "        for account in accounts:\n",
    "            email0 = account[1]\n",
    "            for email in account[2:]:\n",
    "                graph[email0].add(email)  ## 这些 email  对应 同一个人， 等效于 可连通\n",
    "                graph[email].add(email0)\n",
    "\n",
    "        res = []\n",
    "        visited = set()\n",
    "\n",
    "        for account in accounts: \n",
    "            \n",
    "            q = collections.deque([account[1]])\n",
    "            emails = []\n",
    "            while q:\n",
    "                email0 = q.popleft()    \n",
    "                if email0 not in visited:  ## \n",
    "                    visited.add(email0)\n",
    "                    emails.append(email0)\n",
    "                    for neighbor in graph[email0]:  ## 建好图 后， 同一个人的 所有的email 都在这里， 此外 每一个account 里的email 都是 同一 人的。 都要 加上\n",
    "                        q.append(neighbor)\n",
    "                    \n",
    "            if emails: \n",
    "                res.append([account[0]] + sorted(emails))\n",
    "\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge_sort(self, left, right):\n",
    "        res = []\n",
    "        i, j = 0, 0\n",
    "        while i < len(left) and j < len(right):\n",
    "            if left[i] < right[j]:\n",
    "                res.append(left[i])\n",
    "                i += 1\n",
    "            elif left[i] > right[j]:\n",
    "                res.append(right[j])\n",
    "                j += 1\n",
    "            else:\n",
    "                res.append(left[i])\n",
    "                i += 1\n",
    "                j += 1\n",
    "        res += left[i:]\n",
    "        res += right[j:]\n",
    "        return res\n",
    "\n",
    "    def accountsMerge_(self, accounts: List[List[str]]):\n",
    "        if len(accounts) == 1:\n",
    "            res = [accounts[0][0:1] + sorted(set(accounts[0][1:]))]\n",
    "            email_ids = dict((email, 0) for email in res[0][1:])\n",
    "            return res, email_ids\n",
    "        else:\n",
    "            left_res, left_email_ids =  self.accountsMerge_(accounts[:-1])\n",
    "            last_account = accounts[-1]\n",
    "            last_account = last_account[0:1] + sorted(set(last_account[1:]))\n",
    "            to_be_merge_ids = set()\n",
    "            for email in last_account[1:]:\n",
    "                if email in left_email_ids:\n",
    "                    to_be_merge_ids.add(left_email_ids[email])\n",
    "            if not to_be_merge_ids:\n",
    "                for email in last_account[1:]:\n",
    "                    left_email_ids[email] = len(left_res)\n",
    "                left_res.append(last_account)\n",
    "                return left_res, left_email_ids\n",
    "            else:\n",
    "                res = []\n",
    "                buf = []\n",
    "                for i in range(len(left_res)):\n",
    "                    if i in to_be_merge_ids:\n",
    "                        buf = self.merge_sort(buf, left_res[i][1:])\n",
    "                    else:\n",
    "                        res.append(left_res[i])\n",
    "                buf = self.merge_sort(buf, last_account[1:])\n",
    "                res.append(last_account[0:1] + buf)\n",
    "                email_ids = {}\n",
    "                for i, row in enumerate(res):\n",
    "                    for email in row[1:]:\n",
    "                        email_ids[email] = i\n",
    "                return res, email_ids\n",
    "\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        res, _ = self.accountsMerge_(accounts)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        def find(n1):\n",
    "            if n1 != parent[n1]:\n",
    "                parent[n1] = find(parent[n1])\n",
    "            return parent[n1]\n",
    "\n",
    "        parent = {}\n",
    "        account_c = {}\n",
    "        # 拆分\n",
    "        for l_t in accounts:\n",
    "            user = l_t[0]\n",
    "            main_email = l_t[1]\n",
    "            if (user, main_email) not in parent:\n",
    "                parent[(user, main_email)] = (user, main_email)\n",
    "                account_c[(user, main_email)] = [(user, main_email)]\n",
    "            for mail in l_t[2:]:\n",
    "                if (user, mail) not in parent:\n",
    "                    parent[(user, mail)] = (user, mail)\n",
    "                    account_c[(user, mail)] = [(user, mail)]\n",
    "                p1, p2 = find((user, main_email)), find((user, mail))\n",
    "                if p1 != p2:\n",
    "                    parent[p2] = find(p1)\n",
    "                    account_c[p1].extend(account_c[p2])\n",
    "        res = []\n",
    "        for (user, mail) in parent:\n",
    "            if (user, mail) == parent[(user, mail)]:\n",
    "                t_res = [user]\n",
    "                t_others = []\n",
    "                for v in account_c[(user, mail)]:\n",
    "                    t_others.append(v[1])\n",
    "                res.append(t_res + sorted(t_others))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "\n",
    "    def __init__(self, accounts):\n",
    "        n = len(accounts)\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.emails = [None] * n\n",
    "        for i, acc in enumerate(accounts):\n",
    "            self.emails[i] = set(acc[1:])\n",
    "\n",
    "    def union(self, x, y):\n",
    "        px, py = self.find(x), self.find(y)\n",
    "        if px == py:\n",
    "            return\n",
    "        if self.size[px] > self.size[py]:\n",
    "            px, py = py, px\n",
    "        self.parent[px] = py\n",
    "        self.size[py] += self.size[px]\n",
    "        for email in self.emails[px]:\n",
    "            self.emails[py].add(email)\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        n = len(accounts)\n",
    "        uf = UnionFind(accounts)\n",
    "        email_idx = collections.defaultdict(list)\n",
    "        for cur, acc in enumerate(accounts):\n",
    "            for email in acc[1:]:\n",
    "                for pre in email_idx[email]:\n",
    "                    uf.union(pre, cur)\n",
    "                email_idx[email].append(cur)\n",
    "\n",
    "        ans = []\n",
    "        seen = set()\n",
    "        for i in range(n):\n",
    "            pi = uf.find(i)\n",
    "            if pi not in seen:\n",
    "                seen.add(pi)\n",
    "                ans.append(accounts[i][:1] + sorted(uf.emails[pi]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, a: List[List[str]]) -> List[List[str]]:\n",
    "        g = defaultdict(set)\n",
    "        for j in range(len(a)):\n",
    "            b = a[j]\n",
    "            for k in b[1:]:\n",
    "                g[j].add(k)\n",
    "                g[k].add(j) \n",
    "        v = set()\n",
    "        def bfs(x):\n",
    "            if x in v:\n",
    "                return \n",
    "            ans = [x]\n",
    "            v.add(x)\n",
    "            s = [x]\n",
    "            while s:\n",
    "                tmp = []\n",
    "                for j in s:\n",
    "                    for k in g[j]:\n",
    "                        if k not in v:\n",
    "                            v.add(k)\n",
    "                            tmp.append(k)\n",
    "                s = tmp \n",
    "                ans += tmp\n",
    "            return ans \n",
    "        ans = []\n",
    "        for j in g:\n",
    "            if j not in v:\n",
    "                tmp = bfs(j)\n",
    "                b = [k for k in tmp if type(k)==int]\n",
    "                c = [k for k in tmp if type(k)!=int]\n",
    "                b = [a[b[0]][0]]\n",
    "                c.sort()\n",
    "                b += c \n",
    "                \n",
    "                ans.append(b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:   \n",
    "        ## 广度 优先 搜索 (BFS)\n",
    "                ## 建图\n",
    "        graph = collections.defaultdict(set)\n",
    "        for account in accounts:\n",
    "            email0 = account[1]\n",
    "            for email in account[2:]:\n",
    "                graph[email0].add(email)  ## 这些 email  对应 同一个人， 等效于 可连通\n",
    "                graph[email].add(email0)\n",
    "\n",
    "        res = []\n",
    "        visited = set()\n",
    "\n",
    "        for account in accounts: \n",
    "            \n",
    "            q = collections.deque([account[1]])\n",
    "            emails = []\n",
    "            while q:\n",
    "                email0 = q.popleft()    \n",
    "                if email0 not in visited:  ## \n",
    "                    visited.add(email0)\n",
    "                    emails.append(email0)\n",
    "                    for neighbor in graph[email0]:  ## 建好图 后， 同一个人的 所有的email 都在这里， 此外 每一个account 里的email 都是 同一 人的。 都要 加上\n",
    "                        q.append(neighbor)\n",
    "                    \n",
    "            if emails: \n",
    "                res.append([account[0]] + sorted(emails))\n",
    "\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, a: List[List[str]]) -> List[List[str]]:\n",
    "        g = defaultdict(set)\n",
    "        for j in range(len(a)):\n",
    "            b = a[j]\n",
    "            for k in b[1:]:\n",
    "                g[j].add(k)\n",
    "                g[k].add(j) \n",
    "        v = set()\n",
    "        def bfs(x):\n",
    "            if x in v:\n",
    "                return \n",
    "            ans = [x]\n",
    "            v.add(x)\n",
    "            s = [x]\n",
    "            while s:\n",
    "                tmp = []\n",
    "                for j in s:\n",
    "                    for k in g[j]:\n",
    "                        if k not in v:\n",
    "                            v.add(k)\n",
    "                            tmp.append(k)\n",
    "                s = tmp \n",
    "                ans += tmp\n",
    "            return ans \n",
    "        ans = []\n",
    "        for j in g:\n",
    "            if j not in v:\n",
    "                tmp = bfs(j)\n",
    "                b = [k for k in tmp if type(k)==int]\n",
    "                c = [k for k in tmp if type(k)!=int]\n",
    "                b = [a[b[0]][0]]\n",
    "                c.sort()\n",
    "                b += c \n",
    "                \n",
    "                ans.append(b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        # 建立无向图\n",
    "        graph = collections.defaultdict(list)\n",
    "        for account in accounts:\n",
    "            k = account[1]\n",
    "            for email in list(set(account[2:])):\n",
    "                graph[k].append(email)\n",
    "                graph[email].append(k)\n",
    "            \n",
    "        # dfs\n",
    "        def dfs(email,visit,cur_re):\n",
    "            if email in visit:\n",
    "                return\n",
    "            visit.add(email)\n",
    "            cur_re.append(email)\n",
    "            for i in graph[email]:\n",
    "                dfs(i,visit,cur_re)\n",
    "        \n",
    "        # solution\n",
    "        res = []\n",
    "        visited = set()\n",
    "        for account in accounts:\n",
    "            cur_re = []\n",
    "            dfs(account[1],visited,cur_re)\n",
    "            if cur_re:\n",
    "                res.append([account[0]] + sorted(cur_re))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        dict = defaultdict(list)\n",
    "        visited = [False] * len(accounts)\n",
    "        res = []\n",
    "\n",
    "        for i in range(len(accounts)):\n",
    "            for j in range(1, len(accounts[i])):\n",
    "                email = accounts[i][j]\n",
    "                dict[email].append(i)\n",
    "\n",
    "        def dfs(i, emails):\n",
    "            if visited[i]:\n",
    "                return \n",
    "            visited[i] = True\n",
    "            for j in range(1, len(accounts[i])):\n",
    "                email = accounts[i][j]\n",
    "                emails.add(email)\n",
    "                for neighbor in dict[email]:\n",
    "                    dfs(neighbor, emails)\n",
    "        \n",
    "        for i in range(len(accounts)):\n",
    "            if visited[i]:\n",
    "                continue\n",
    "            name, emails = accounts[i][0], set()\n",
    "            dfs(i, emails)\n",
    "            res.append([name] + sorted(emails))\n",
    "        return res \n",
    "                \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: list[list[str]]) -> list[list[str]]:\n",
    "        dic=collections.defaultdict(list)\n",
    "        for account in accounts:\n",
    "            main=account[1]\n",
    "            for email in account[2:]:\n",
    "                dic[main].append(email)\n",
    "                dic[email].append(main)\n",
    "        def dfs(email,ans,visited):\n",
    "            if email in visited:\n",
    "                return \n",
    "            visited.add(email)\n",
    "            ans.append(email)\n",
    "            for neigh in dic[email]:\n",
    "                dfs(neigh,ans,visited)\n",
    "        ans=[]\n",
    "        visited=set()\n",
    "        for account in accounts:\n",
    "            temp=[]\n",
    "            if account[1] not in visited:\n",
    "                dfs(account[1],temp,visited)\n",
    "                ans.append([account[0]]+sorted(temp))\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        \n",
    "\n",
    "# 建图，我们可以忽略姓名，直接把关联的账户连接起来即可\n",
    "# 对每一个 account 子数组的第一个邮箱进行深度优先搜索，子数组的姓名+得到的账户组（也要再排个序） 就是这个人对应的答案\n",
    "\n",
    "# dfs\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        def build_graph(accounts):\n",
    "            graph = collections.defaultdict(set)\n",
    "            for account in accounts:\n",
    "                first = account[1]\n",
    "                for email in account[2:]:\n",
    "                    graph[first].add(email)\n",
    "                    graph[email].add(first)\n",
    "            return graph\n",
    "\n",
    "        def dfs(email, graph, visited):\n",
    "            if email in visited:\n",
    "                return []\n",
    "            visited.add(email)\n",
    "            emails = [email]\n",
    "\n",
    "            for neighbor in graph[email]:\n",
    "                emails += dfs(neighbor, graph, visited)\n",
    "\n",
    "            return emails\n",
    "\n",
    "        graph = build_graph(accounts)\n",
    "        res = []\n",
    "        visited = set()\n",
    "        for account in accounts:\n",
    "            emails = dfs(account[1], graph, visited)\n",
    "            if emails:\n",
    "                res.append([account[0]] + sorted(emails))\n",
    "        return res\n",
    "\n",
    "# 直接暴力地把 (姓名，邮箱) 当作并查集字典中的 key，再额外维护一个字典，以每个集合的根节点作为 key，存储每个集合中所有的 (姓名，邮箱)。\n",
    "# 每次合并集合的时候除了更新根节点外，还要更新根节点对应的 (姓名，邮箱)\n",
    "# 最后添加答案的时候别忘了对这个人的所有邮箱排序。\n",
    "\n",
    "# 并查集\n",
    "# class UnionFind:\n",
    "#     def __init__(self, n) -> None:\n",
    "#         self.parent = list(range(n + 1))\n",
    "#         # self.parent = collections.defaultdict()\n",
    "\n",
    "#     def find(self, x):\n",
    "#         if self.parent[x] != x:\n",
    "#             self.parent[x] = self.find(self.parent[x])\n",
    "#         return self.parent[x]\n",
    "\n",
    "#     def union(self, x, y):\n",
    "#         x = self.find(x)\n",
    "#         y = self.find(y)\n",
    "#         self.parent[x] = y\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "#         n = len(accounts)\n",
    "#         uf = UnionFind(n + 1)\n",
    "#         lookup = {}\n",
    "#         for id, account in enumerate(accounts):\n",
    "#             # name = account[0]\n",
    "#             emails = account[1:]\n",
    "#             for email in emails:\n",
    "#                 if email in lookup:\n",
    "#                     uf.union(id, lookup[email])\n",
    "#                 else:\n",
    "#                     lookup[email] = id\n",
    "\n",
    "#         joinSet = collections.defaultdict(set)\n",
    "#         for i in range(n):\n",
    "#             id = uf.find(i)\n",
    "#             for email in accounts[i][1:]:\n",
    "#                 joinSet[id].add(email)\n",
    "\n",
    "#         res = []\n",
    "#         for id, emails in joinSet.items():\n",
    "#             list(emails).sort()\n",
    "#             res.append([accounts[id][0]] + sorted(list(emails)))\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        # dfs\n",
    "        # 建图，我们可以忽略姓名，直接把关联的账户连接起来即可\n",
    "        # 对每一个 account 子数组的第一个邮箱进行深度优先搜索，子数组的姓名+得到的账户组（也要再排个序） 就是这个人对应的答案\n",
    "        def build_graph():\n",
    "            graph = defaultdict(list)\n",
    "            for account in accounts:\n",
    "                master = account[1]\n",
    "                for email in set(account[2:]):\n",
    "                    graph[master].append(email)\n",
    "                    graph[email].append(master)\n",
    "            return graph\n",
    "\n",
    "        def dfs(email, visited, emails):\n",
    "            if email in visited:\n",
    "                return\n",
    "            visited.add(email)\n",
    "            emails.append(email)\n",
    "            for nex in graph[email]:\n",
    "                dfs(nex, visited, emails)\n",
    "\n",
    "        graph = build_graph()\n",
    "        res = []\n",
    "        visited = set()\n",
    "        for account in accounts:\n",
    "            emails = []\n",
    "            dfs(account[1], visited, emails)\n",
    "            if emails:\n",
    "                res.append([account[0]] + sorted(emails))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        edges = dict()\n",
    "        for i, account_1 in enumerate(accounts):\n",
    "            edges[i] = []\n",
    "            for j in range(0, len(accounts)):\n",
    "                account_2  = accounts[j]\n",
    "                if account_1[0] == account_2[0] and i!=j:\n",
    "                    set_1 = set(account_1[1:])\n",
    "                    set_2 = set(account_2[1:])\n",
    "                    if (len(set_1|set_2) != len(set_1) + len(set_2)):\n",
    "                        edges[i].append(j)\n",
    "        visited = set()\n",
    "        def dfs(startIdx, tmp_):\n",
    "            for i in edges[startIdx]:\n",
    "                if i not in visited:\n",
    "                    visited.add(i)\n",
    "                    for candi in accounts[i]:\n",
    "                        if candi == accounts[startIdx][0]:\n",
    "                            pass\n",
    "                        else:\n",
    "                            tmp_.add(candi)\n",
    "                    dfs(i, tmp_)\n",
    "        res = []\n",
    "        for i in range(len(accounts)):\n",
    "            if i not in visited:\n",
    "                visited.add(i)\n",
    "                tmp = set(accounts[i][1:])\n",
    "                dfs(i, tmp)\n",
    "                res.append([accounts[i][0]] + sorted(list(tmp)))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "\n",
    "        # 深度优先遍历。\n",
    "        def dfs(cur_email, graph, email_list):\n",
    "            if cur_email in seen:     \n",
    "                return email_list\n",
    "\n",
    "            seen.add(cur_email)  \n",
    "            email_list.append(cur_email)  \n",
    "\n",
    "            # 对每个邻居， 都去深搜一下。\n",
    "            for neighbour in graph[cur_email]:\n",
    "                dfs(neighbour, graph, email_list)\n",
    "\n",
    "        # 构建无向图，每个邮箱为一个节点， 同一个账户的邮箱全部相连。\n",
    "        # 有多少联通分量，就有多少独立的账户\n",
    "        # 构建图，这部分应该是固定写法。\n",
    "\n",
    "        # g = {\"邮箱\"：[\"与此相连的所有邮箱\"...]}\n",
    "        g =  defaultdict(list)\n",
    "        for acc in accounts:\n",
    "            master = acc[1]  # 选取第一个邮箱作为键\n",
    "            for email in list(set(acc[2:])):\n",
    "                g[master].append(email)\n",
    "                g[email].append(master)  # 这里写的其实很巧妙。把数据很完整地统计进来。\n",
    "\n",
    "        ret = []\n",
    "        seen = set()\n",
    "\n",
    "        for acc in accounts:\n",
    "            cur_ret = []\n",
    "\n",
    "            # 这里就写为这样！ 让 dfs() 来改变 cur_ret 的值。\n",
    "            dfs(acc[1], g, cur_ret)\n",
    "\n",
    "            if cur_ret:\n",
    "                ret.append([acc[0]] + sorted(cur_ret))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        def build_graph(accounts):\n",
    "            graph = collections.defaultdict(set)\n",
    "            for account in accounts:\n",
    "                first = account[1]\n",
    "                for email in account[2:]:\n",
    "                    graph[first].add(email)\n",
    "                    graph[email].add(first)\n",
    "            return graph\n",
    "\n",
    "        def dfs(email, graph, visited):\n",
    "            if email in visited:\n",
    "                return []\n",
    "            visited.add(email)\n",
    "            emails = [email]\n",
    "\n",
    "            for neighbor in graph[email]:\n",
    "                emails += dfs(neighbor, graph, visited)\n",
    "\n",
    "            return emails\n",
    "\n",
    "        graph = build_graph(accounts)\n",
    "        res = []\n",
    "        visited = set()\n",
    "        for account in accounts:\n",
    "            emails = dfs(account[1], graph, visited)\n",
    "            if emails:\n",
    "                res.append([account[0]] + sorted(emails))\n",
    "        return res\n",
    "\n",
    "\n",
    "# 并查集\n",
    "# class UnionFind:\n",
    "#     def __init__(self, n) -> None:\n",
    "#         self.parent = list(range(n + 1))\n",
    "#         # self.parent = collections.defaultdict()\n",
    "\n",
    "#     def find(self, x):\n",
    "#         if self.parent[x] != x:\n",
    "#             self.parent[x] = self.find(self.parent[x])\n",
    "#         return self.parent[x]\n",
    "\n",
    "#     def union(self, x, y):\n",
    "#         x = self.find(x)\n",
    "#         y = self.find(y)\n",
    "#         self.parent[x] = y\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "#         n = len(accounts)\n",
    "#         uf = UnionFind(n + 1)\n",
    "#         lookup = {}\n",
    "#         for id, account in enumerate(accounts):\n",
    "#             # name = account[0]\n",
    "#             emails = account[1:]\n",
    "#             for email in emails:\n",
    "#                 if email in lookup:\n",
    "#                     uf.union(id, lookup[email])\n",
    "#                 else:\n",
    "#                     lookup[email] = id\n",
    "\n",
    "#         joinSet = collections.defaultdict(set)\n",
    "#         for i in range(n):\n",
    "#             id = uf.find(i)\n",
    "#             for email in accounts[i][1:]:\n",
    "#                 joinSet[id].add(email)\n",
    "\n",
    "#         res = []\n",
    "#         for id, emails in joinSet.items():\n",
    "#             list(emails).sort()\n",
    "#             res.append([accounts[id][0]] + sorted(list(emails)))\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        emails_accounts_map = defaultdict(list)\n",
    "        visited = [False] * len(accounts)\n",
    "        res = []\n",
    "\n",
    "        for i, account in enumerate(accounts):\n",
    "            for j in range(1, len(account)):\n",
    "                email = account[j]\n",
    "                emails_accounts_map[email].append(i)\n",
    "\n",
    "        def dfs(i, emails):\n",
    "            if visited[i]:\n",
    "                return\n",
    "            visited[i] = True\n",
    "            for j in range(1, len(accounts[i])):\n",
    "                email = accounts[i][j]\n",
    "                emails.add(email)\n",
    "                for neighbor in emails_accounts_map[email]:\n",
    "                    dfs(neighbor, emails)\n",
    "\n",
    "        for i, account in enumerate(accounts):\n",
    "            if visited[i]:\n",
    "                continue\n",
    "            name, emails = account[0], set()\n",
    "            dfs(i, emails)\n",
    "            res.append([name] + sorted(emails))\n",
    "        return res\n",
    "\n",
    "# leetcode submit region end(Prohibit modification and deletion)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        edges = dict()\n",
    "        for i, account_1 in enumerate(accounts):\n",
    "            edges[i] = []\n",
    "            for j in range(0, len(accounts)):\n",
    "                account_2  = accounts[j]\n",
    "                if account_1[0] == account_2[0] and i!=j:\n",
    "                    set_1 = set(account_1[1:])\n",
    "                    set_2 = set(account_2[1:])\n",
    "                    if (len(set_1|set_2) != len(set_1) + len(set_2)):\n",
    "                        edges[i].append(j)\n",
    "        visited = set()\n",
    "        def dfs(startIdx, tmp_):\n",
    "            for i in edges[startIdx]:\n",
    "                if i not in visited:\n",
    "                    visited.add(i)\n",
    "                    for candi in accounts[i]:\n",
    "                        if candi == accounts[startIdx][0]:\n",
    "                            pass\n",
    "                        else:\n",
    "                            tmp_.add(candi)\n",
    "                    dfs(i, tmp_)\n",
    "        res = []\n",
    "        for i in range(len(accounts)):\n",
    "            if i not in visited:\n",
    "                visited.add(i)\n",
    "                tmp = set(accounts[i][1:])\n",
    "                dfs(i, tmp)\n",
    "                res.append([accounts[i][0]] + sorted(list(tmp)))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        g=collections.defaultdict(list)\n",
    "        for a in accounts:\n",
    "            master = a[1]\n",
    "            for email in set(a[2:]):\n",
    "                g[master].append(email)\n",
    "                g[email].append(master)\n",
    "\n",
    "        def dfs(cur,vis,path):\n",
    "            if cur in vis:\n",
    "                return\n",
    "            vis.add(cur)\n",
    "            path.append(cur)\n",
    "            for n in g[cur]:\n",
    "                dfs(n,vis,path)\n",
    "        vis=set()\n",
    "        ans=[]\n",
    "        for a in accounts:\n",
    "            path=[]\n",
    "            dfs(a[1],vis,path)\n",
    "            if len(path)!=0:\n",
    "                ans.append([a[0]]+sorted(path))\n",
    "        return ans\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        dic = {}\n",
    "        ans = []\n",
    "        visited = set()\n",
    "        for i in range(len(accounts)):\n",
    "            for email in accounts[i][1:]:\n",
    "                if email in dic:\n",
    "                    dic[email].append(i)\n",
    "                else:\n",
    "                    dic[email] = [i]\n",
    "        for i in range(len(accounts)):\n",
    "            if i in visited:\n",
    "                continue\n",
    "            else:\n",
    "                ans.append([accounts[i][0]])\n",
    "                address = set()\n",
    "                dq = collections.deque([i])\n",
    "                while dq:\n",
    "                    index = dq.popleft()\n",
    "                    visited.add(index)\n",
    "                    for email in accounts[index][1:]:\n",
    "                        address.add(email)\n",
    "                        for line in dic[email]:\n",
    "                            if line not in visited:\n",
    "                                dq.append(line)\n",
    "                address = sorted(list(address))\n",
    "                ans[-1] += address\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "\n",
    "        fa = {}\n",
    "        acc = {}\n",
    "        \n",
    "        def find(a):\n",
    "            if fa[a] != a:\n",
    "                fa[a] = find(fa[a])\n",
    "\n",
    "            return fa[a]\n",
    "\n",
    "        def union(a, b):\n",
    "            pa, pb = find(a), find(b)\n",
    "            if pa == pb: return \n",
    "\n",
    "            fa[pa] = pb\n",
    "            acc[pb] += acc[pa]\n",
    "            del acc[pa]\n",
    "            return \n",
    "\n",
    "        def add(user, master):\n",
    "            if (user, master) not in fa: # only consider new nodes \n",
    "                acc[(user, master)] = [(user, master)]\n",
    "                fa[(user, master)] = (user, master)\n",
    "\n",
    "        \n",
    "        for account in accounts:\n",
    "            user, master = account[0], account[1]\n",
    "            add(user, master)\n",
    "\n",
    "            aa = list(set(account[2:]))\n",
    "            for i in range(len(aa)):\n",
    "                add(user, aa[i])\n",
    "                union((user, master), (user, aa[i]))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        res = []\n",
    "        for root, val in fa.items():\n",
    "            if root == val: # consider only root nodes \n",
    "                user = acc[root][0][0]\n",
    "                tmp = []\n",
    "                for account in acc[root]:\n",
    "                    tmp.append(account[1])\n",
    "\n",
    "                res.append([user] + sorted(tmp))\n",
    "        return res\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        # child2master = {} # we create this so that we can union these accounts\n",
    "        master2person = {}\n",
    "\n",
    "        master2child = defaultdict(list)\n",
    "\n",
    "        for account in accounts:\n",
    "            name, master = account[0], account[1]\n",
    "            master2person[master] = person\n",
    "            if len(account) > 2: # has childern accounts\n",
    "                for i in range(2, len(account)):\n",
    "                    master2child[master].append(account[i])\n",
    "\n",
    "        # union\n",
    "\n",
    "\n",
    "        res = []\n",
    "        # create output\n",
    "        for master in child2master.values():\n",
    "            # for each unique master, find it's account person\n",
    "            person = master2person[master]\n",
    "            emails = master2child[master] + [master]\n",
    "            res.append([person] + emails)\n",
    "\n",
    "\n",
    "        return res\n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        # build graph\n",
    "        graph = defaultdict(list)\n",
    "        for account in accounts:\n",
    "            name, master = account[0], account[1]\n",
    "            for email in account[2:]:\n",
    "                graph[master].append(email)\n",
    "                graph[email].append(master)\n",
    "        visited = []\n",
    "        emails = []\n",
    "        def dfs(email):\n",
    "            if email in visited:\n",
    "                return\n",
    "            visited.append(email)\n",
    "            emails.append(email)\n",
    "            for child in graph[email]:\n",
    "                if child not in visited:\n",
    "                    dfs(child)\n",
    "        res = []\n",
    "        for item in accounts:\n",
    "            name = item[0]\n",
    "            dfs(item[1])\n",
    "\n",
    "            if emails:\n",
    "                res.append([name] + sorted(emails))\n",
    "            emails.clear()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#相同邮箱的账号一定属于同一个人，所以只能用邮箱来判断！\n",
    "#名称相同的账户不一定属于同一个人\n",
    "class DSU(object):\n",
    "    def __init__(self, n):\n",
    "        self.par = [i for i in range(n)]\n",
    "        self.rnk = [0] * n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.par[x] != x:\n",
    "            self.par[x] = self.find(self.par[x]) #状态压缩，递归继续找最根的位置，直接指向根节点\n",
    "        return self.par[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        xr, yr = self.find(x), self.find(y)\n",
    "        if self.rnk[xr] < self.rnk[yr]: #希望平衡，把矮的接到高的上面去\n",
    "            self.par[xr] = yr\n",
    "        elif self.rnk[xr] > self.rnk[yr]:\n",
    "            self.par[yr] = xr\n",
    "        else:\n",
    "            self.par[yr] = xr\n",
    "            self.rnk[xr] += 1\n",
    "\n",
    "class Solution(object):\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        uf = DSU(len(accounts))\n",
    "        email_id = dict()  #{email: index} #下面是在更新这个dic的index\n",
    "        #根据email合并，但email又不是数字所以得用index合并\n",
    "        for index, account in enumerate(accounts):\n",
    "            for email in account[1:]:\n",
    "                if email in email_id: #如果出现过了，证明这两个email是属于同一个account id(即index)的那么就合并他们\n",
    "                    uf.union(email_id[email], index)\n",
    "                else:\n",
    "                    email_id[email] = index\n",
    "        print(email_id)            \n",
    "        id_email = collections.defaultdict(list)   #{index: [emailList]}\n",
    "        for email, index in email_id.items():\n",
    "            id_email[uf.find(index)].append(email)  # 注意这里id_email的key\n",
    "        print(id_email)  \n",
    "        return [[accounts[i][0]] + sorted(e) for i, e in id_email.items()]\n",
    "\n",
    "class Solution(object):\n",
    "    def accountsMerge(self, accounts):\n",
    "        from collections import defaultdict\n",
    "        visited_accounts = [False] * len(accounts)\n",
    "        emails_accounts_map = defaultdict(list)\n",
    "        res = []\n",
    "        # Build up the graph.\n",
    "        for i, account in enumerate(accounts):\n",
    "            for j in range(1, len(account)):\n",
    "                email = account[j]\n",
    "                emails_accounts_map[email].append(i)\n",
    "#因为是按照email来merge的，所以以email为key，index为value聚合到list里\n",
    "# emails_accounts_map = defaultdict(list,\n",
    "#            {'johnsmith@mail.com': [0, 2],\n",
    "#             'john00@mail.com': [0],\n",
    "#             'johnnybravo@mail.com': [1],\n",
    "#             'john_newyork@mail.com': [2],\n",
    "#             'mary@mail.com': [3]})\n",
    "        # DFS code for traversing accounts.\n",
    "        def dfs(i, emails):\n",
    "            if visited_accounts[i]: #注意\n",
    "                return\n",
    "            visited_accounts[i] = True  #访问过了这个账户就标记true\n",
    "            for j in range(1, len(accounts[i])):\n",
    "                email = accounts[i][j] #遍历每个email\n",
    "                emails.add(email)  #把email加进去\n",
    "                for neighbor in emails_accounts_map[email]: #再去查这个email对应的account\n",
    "                    dfs(neighbor, emails) #继续查别的\n",
    "        # Perform DFS for accounts and add to results.\n",
    "        for i, account in enumerate(accounts): #一个个来遍历\n",
    "            if visited_accounts[i]:  #如果visit过了，那么就不加\n",
    "                continue\n",
    "            name, emails = account[0], set()  \n",
    "            dfs(i, emails) #查第一个账户!\n",
    "            res.append([name] + sorted(emails)) #查完了之后append\n",
    "        return res\n",
    "#时间：快排最后Σnlogn（dominant了），其实前面都只有n的build graph\n",
    "#空间：Σn  存储n个account"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.com/problems/accounts-merge/discuss/2399320/Python-A-17-line-solution-using-DFS-and-python-dict-as-a-Directed-Graph\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        \n",
    "        def dfs(node):\n",
    "            if node not in graph:\n",
    "                return []\n",
    "            \n",
    "            out = [node]\n",
    "            for neighbor in graph.pop(node):\n",
    "                out += dfs(neighbor)\n",
    "            return out\n",
    "        \n",
    "        graph = defaultdict(list)\n",
    "        for acc in accounts:\n",
    "            for i in range(1, len(acc) - 1):\n",
    "                graph[acc[i]].append(acc[i + 1])\n",
    "            graph[acc[-1]].append(acc[1])\n",
    "        \n",
    "        ans = []\n",
    "        for acc in accounts:\n",
    "            if acc[1] in graph:\n",
    "                ans.append([acc[0], *sorted(dfs(acc[1]))])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        edges = dict()\n",
    "        for i, account_1 in enumerate(accounts):\n",
    "            edges[i] = []\n",
    "            for j in range(0, len(accounts)):\n",
    "                account_2  = accounts[j]\n",
    "                if account_1[0] == account_2[0] and i!=j:\n",
    "                    set_1 = set(account_1[1:])\n",
    "                    set_2 = set(account_2[1:])\n",
    "                    if (len(set_1|set_2) != len(set_1) + len(set_2)):\n",
    "                        edges[i].append(j)\n",
    "        visited = set()\n",
    "        def dfs(startIdx, tmp_):\n",
    "            for i in edges[startIdx]:\n",
    "                if i not in visited:\n",
    "                    visited.add(i)\n",
    "                    for candi in accounts[i]:\n",
    "                        if candi == accounts[startIdx][0]:\n",
    "                            pass\n",
    "                        else:\n",
    "                            tmp_.add(candi)\n",
    "                    dfs(i, tmp_)\n",
    "        res = []\n",
    "        for i in range(len(accounts)):\n",
    "            if i not in visited:\n",
    "                visited.add(i)\n",
    "                tmp = set(accounts[i][1:])\n",
    "                dfs(i, tmp)\n",
    "                res.append([accounts[i][0]] + sorted(list(tmp)))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.com/problems/accounts-merge/solutions/2399320/Python-A-17-line-solution-using-DFS-and-python-dict-as-a-Directed-Graph\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        d = defaultdict(list)\n",
    "        for xs in accounts:\n",
    "            for i in range(1, len(xs) - 1):\n",
    "                d[xs[i]].append(xs[i + 1])\n",
    "            d[xs[-1]].append(xs[1])\n",
    "        \n",
    "        def dfs(x):\n",
    "            if x not in d:\n",
    "                return []\n",
    "            \n",
    "            ans = [x]\n",
    "            for nei in d.pop(x):\n",
    "                ans += dfs(nei)\n",
    "            return ans\n",
    "        \n",
    "        ans = []\n",
    "        for xs in accounts:\n",
    "            if xs[1] in d:\n",
    "                ans.append([xs[0], *sorted(dfs(xs[1]))])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        record = collections.defaultdict(list)\n",
    "        for item in accounts:\n",
    "            for emal in item[2:]:\n",
    "                record[item[1]].append(emal)\n",
    "                record[emal].append(item[1])\n",
    "        def dfs(email,tem):\n",
    "            if email in visit:\n",
    "                return\n",
    "            visit.add(email)\n",
    "            tem.append(email)\n",
    "            for e in record[email]:\n",
    "                dfs(e,tem)\n",
    "\n",
    "        visit = set()\n",
    "        res = []\n",
    "        for account in accounts:\n",
    "            tem = []\n",
    "            dfs(account[1],tem)\n",
    "            if tem:\n",
    "                res.append([account[0]] + sorted(tem))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        visited = set()\n",
    "        email2idx = collections.defaultdict(list)\n",
    "        res = []\n",
    "        def dfs(idx, emails):\n",
    "            if idx in visited:\n",
    "                return\n",
    "            visited.add(idx)\n",
    "            for email in accounts[idx][1:]:\n",
    "                emails.add(email)\n",
    "                for i in email2idx[email]:\n",
    "                    dfs(i, emails)\n",
    "\n",
    "        for idx, account in enumerate(accounts):\n",
    "            for email in account[1:]:\n",
    "                email2idx[email].append(idx)\n",
    "        \n",
    "        for idx, account in enumerate(accounts):\n",
    "            name = account[0]\n",
    "            emails = set()\n",
    "            if idx not in visited:\n",
    "                dfs(idx, emails)\n",
    "                res.append([name] + sorted(list(emails)))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        email2Idx = collections.defaultdict(list)\n",
    "        n = len(accounts)\n",
    "        visited = set()\n",
    "        res = []\n",
    "        for i, acc in enumerate(accounts):\n",
    "            for email in acc[1:]:\n",
    "                email2Idx[email].append(i)\n",
    "        def dfs(idx, emails):\n",
    "            if idx in visited:\n",
    "                return\n",
    "            lst = accounts[idx][1:]\n",
    "            visited.add(idx)\n",
    "            for email in lst:\n",
    "                emails.add(email)\n",
    "                for nxt in email2Idx[email]:\n",
    "                    dfs(nxt, emails)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                name = accounts[i][0]\n",
    "                emails = set()\n",
    "                dfs(i, emails)\n",
    "                res.append([name] + sorted(list(emails)))\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        g = defaultdict(list)\n",
    "        for _,mst,*a in accounts:\n",
    "            for eml in set([*a]):\n",
    "                g[mst].append(eml)\n",
    "                g[eml].append(mst)\n",
    "        \n",
    "        def dfs(x):\n",
    "            if x in vis:\n",
    "                return\n",
    "            vis.add(x)\n",
    "            emls.append(x)\n",
    "            for y in g[x]:\n",
    "                dfs(y)\n",
    "        ans = []\n",
    "        vis = set()\n",
    "        for act in accounts:\n",
    "            emls = []\n",
    "            dfs(act[1])\n",
    "            if emls:\n",
    "                ans.append([act[0]]+sorted(emls))\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a in accounts:\n",
    "            master = a[1]\n",
    "            for e in list(set(a[2:])):\n",
    "                graph[master].append(e)\n",
    "                graph[e].append(master)\n",
    "        res = []\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(e,emails):\n",
    "            if e in visited:\n",
    "                return\n",
    "            visited.add(e)\n",
    "            emails.append(e)\n",
    "            for i in graph[e]:\n",
    "                dfs(i,emails)\n",
    "            \n",
    "        for a in accounts:\n",
    "            emails = []\n",
    "            dfs(a[1],emails)\n",
    "            if emails:\n",
    "                res.append([a[0]]+sorted(emails))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\r\n",
    "\r\n",
    "from collections import defaultdict\r\n",
    "class Solution:\r\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\r\n",
    "        mail2idxs = defaultdict(list)\r\n",
    "        for idx, i in enumerate(accounts):\r\n",
    "            for mail in i[1:]:\r\n",
    "                mail2idxs[mail].append(idx)\r\n",
    "        # dfs\r\n",
    "        idx2idxs = defaultdict(list)\r\n",
    "        for i in mail2idxs.values():\r\n",
    "            for j in i:\r\n",
    "                idx2idxs[j].extend(i)\r\n",
    "        for k, v in mail2idxs.items():\r\n",
    "            mail2idxs[k] = set(v)\r\n",
    "        print(mail2idxs)\r\n",
    "        \r\n",
    "        res = []\r\n",
    "        visited = set()\r\n",
    "        def dfs(idx, cur: List):\r\n",
    "            cur.append(idx)\r\n",
    "            visited.add(idx)\r\n",
    "            for i in idx2idxs[idx]:\r\n",
    "                if i not in visited:\r\n",
    "                    dfs(i, cur)\r\n",
    "        for i in range(len(accounts)):\r\n",
    "            if i not in visited:\r\n",
    "                one_person = []\r\n",
    "                dfs(i, one_person)\r\n",
    "                email = []\r\n",
    "                for each in one_person:\r\n",
    "                    email.extend(accounts[each][1:])\r\n",
    "                \r\n",
    "                res.append([accounts[i][0]] + sorted(set(email)))\r\n",
    "                \r\n",
    "                    \r\n",
    "        return res\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "print(Solution().accountsMerge(accounts = [[\"John\", \"johnsmith@mail.com\", \"john00@mail.com\"], [\"John\", \"johnnybravo@mail.com\"], [\"John\", \"johnsmith@mail.com\", \"john_newyork@mail.com\"], [\"Mary\", \"mary@mail.com\"]]))                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        g = defaultdict(list)\n",
    "        for acc in accounts:\n",
    "            root = acc[1]\n",
    "            for email in acc[2:]:\n",
    "                g[root].append(email)\n",
    "                g[email].append(root)\n",
    "        def dfs(e):\n",
    "            for neighbour in g[e]:\n",
    "                if neighbour not in visited:\n",
    "                    emails.append(neighbour)\n",
    "                    visited.add(neighbour)\n",
    "                    dfs(neighbour)\n",
    "        res = []\n",
    "        visited = set()\n",
    "        for acc in accounts:\n",
    "            name = acc[0]\n",
    "            emails = []\n",
    "            if acc[1] not in visited:\n",
    "                emails.append(acc[1])\n",
    "                visited.add(acc[1])\n",
    "                dfs(acc[1])\n",
    "            if emails:\n",
    "                res.append([name] + sorted(emails[:]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def build_graph(self,accounts):\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        for account in accounts:\n",
    "            master = account[1]\n",
    "            # 对剩余账户做一个去重\n",
    "            for email in list(set(account[2:])):\n",
    "                graph[master].append(email)\n",
    "                graph[email].append(master)\n",
    "        \n",
    "        return graph\n",
    "    \n",
    "    \n",
    "    \n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        def dfs(email):\n",
    "            \"\"\"\n",
    "            深搜遍历\n",
    "            \"\"\"\n",
    "            # 已经访问过的就剪枝\n",
    "            if email in visited:\n",
    "                return \n",
    "            \n",
    "            visited.add(email)\n",
    "            emails.append(email)\n",
    "            \n",
    "            # 对邻居节点继续深搜\n",
    "            for neighbor in graph[email]:\n",
    "                dfs(neighbor)\n",
    "\n",
    "        graph = self.build_graph(accounts)\n",
    "        res = []\n",
    "        visited = set()\n",
    "        for account in accounts:\n",
    "            emails = []\n",
    "            dfs(account[1])\n",
    "            if emails:\n",
    "                res.append([account[0]] + sorted(emails))\n",
    "        \n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
